Wy Online Judge

WyOJ

ID	题目	提交者	结果	用时	内存	语言	文件大小	提交时间	测评时间
#389	#37. 「NOIP2009」最优贸易	j27eGU	100	765ms	8516kb	C++23	1.3kb	2025-04-23 11:36:43	2025-04-23 11:36:44

answer

#include<bits/stdc++.h>
using namespace std;
#define MAXN 100010
vector <int> g[MAXN],_g[MAXN];
int n,m,p[MAXN],maxn[MAXN],minn[MAXN];
bool inq[MAXN];
queue <int> q;
void spfa1(int s)
{
	memset(inq,0,sizeof(inq));
	memset(minn,0x3f,sizeof(minn));
	while(!q.empty())q.pop();
	q.push(s);
	minn[s]=p[s];
	inq[s]=1;
	while(!q.empty())
	{
		int u=q.front();
		q.pop();
		inq[u]=0;
		for(int i=0;i<g[u].size();i++)
		{
			int v=g[u][i];
			if(minn[v]>min(minn[u],p[v]))
			{
				minn[v]=min(minn[u],p[v]);
				if(!inq[v])q.push(v),inq[v]=1;
			}
		}
	}
}
void spfa2(int s)
{
	memset(inq,0,sizeof(inq));
	memset(maxn,-0x3f,sizeof(maxn));
	while(!q.empty())q.pop();
	q.push(s);
	maxn[s]=p[s];
	inq[s]=1;
	while(!q.empty())
	{
		int u=q.front();
		q.pop();
		inq[u]=0;
		for(int i=0;i<_g[u].size();i++)
		{
			int v=_g[u][i];
			if(maxn[v]<max(maxn[u],p[v]))
			{
				maxn[v]=max(maxn[u],p[v]);
				if(!inq[v])q.push(v),inq[v]=1;
			}
		}
	}
}
int main()
{
	cin>>n>>m;
	for(int i=1;i<=n;i++)cin>>p[i];
	for(int i=1;i<=m;i++)
	{
		int u,v,w;
		cin>>u>>v>>w;
		g[u].push_back(v);
		_g[v].push_back(u);
		if(w==2)g[v].push_back(u),_g[u].push_back(v);
	}
	spfa1(1);
	spfa2(n);
	int ans=0;
	for(int i=1;i<=n;i++)ans=max(ans,maxn[i]-minn[i]);
	cout<<ans;
	return 0;
}

源文件, 语言: C++23

详细

小提示：点击横条可展开更详细的信息

Test #1:

score: 10

Accepted

time: 1ms

memory: 4356kb

input:

6 6
100 64 47 50 57 1
1 2 1
2 3 1
1 3 1
1 4 1
1 5 1
5 6 1

output:

result:

ok 1 number(s): "0"

Test #2:

score: 10

Accepted

time: 5ms

memory: 4304kb

input:

10 20
100 89 100 72 39 50 74 50 50 1
1 2 1
1 3 1
1 4 1
2 5 1
1 5 1
3 5 1
2 3 1
2 4 1
3 4 1
4 5 1
1 6...

output:

result:

ok 1 number(s): "24"

Test #3:

score: 10

Accepted

time: 13ms

memory: 4444kb

input:

1000 5000
100 73 41 70 51 27 23 31 15 36 90 58 36 12 55 27 2 41 78 98 88 20 66 70 18 82 97 98 1 89 7...

output:

result:

ok 1 number(s): "8"

Test #4:

score: 10

Accepted

time: 128ms

memory: 6184kb

input:

10000 100000
100 33 61 93 55 29 44 93 70 28 5 55 84 98 90 37 29 30 95 29 30 31 43 25 65 99 70 49 22 ...

output:

result:

ok 1 number(s): "13"

Test #5:

score: 10

Accepted

time: 159ms

memory: 8204kb

input:

50000 100000
100 90 26 38 9 47 89 99 3 27 3 64 29 28 47 27 72 3 79 64 35 68 62 21 11 19 26 11 23 33 ...

output:

result:

ok 1 number(s): "4"

Test #6:

score: 10

Accepted

time: 0ms

memory: 4388kb

input:

100 500
100 79 81 43 61 74 4 42 11 37 27 27 5 30 30 22 3 49 69 79 88 28 91 80 51 18 45 19 20 99 50 1...

output:

result:

ok 1 number(s): "5"

Test #7:

score: 10

Accepted

time: 24ms

memory: 4516kb

input:

1000 10000
100 12 34 95 100 42 16 23 29 20 98 32 19 6 26 20 32 49 79 98 40 89 63 4 75 34 42 44 86 20...

output:

result:

ok 1 number(s): "15"

Test #8:

score: 10

Accepted

time: 79ms

memory: 7688kb

input:

10000 50000
100 91 15 100 2 73 60 37 87 92 48 67 18 53 76 63 39 62 77 50 71 66 68 90 9 34 54 36 46 7...

output:

result:

ok 1 number(s): "17"

Test #9:

score: 10

Accepted

time: 190ms

memory: 8516kb

input:

50000 100000
100 100 77 48 5 26 42 78 18 51 73 96 40 1 38 12 75 88 77 34 85 29 37 30 37 68 81 36 89 ...

output:

result:

ok 1 number(s): "16"

Test #10:

score: 10

Accepted

time: 166ms

memory: 8444kb

input:

50000 100000
100 15 57 29 70 54 80 43 98 13 1 21 27 21 40 10 5 79 99 15 2 37 15 59 35 86 87 77 28 4 ...

output:

result:

ok 1 number(s): "2"