P1073

崔冷亦

[C++] 纯文本查看 复制代码

#include<iostream>
#include<cstring>
#include<queue>
using namespace std;
int n,m,cnt,h1[900001],h2[900001],mid,f1[900001],f2[900001],ans=-0x3f3f3f3f;
int j[900001];
bool b[900001];
struct edge{
	int n,t;
}a1[900001],a2[900001];
void add1(int f,int t)
{
	a1[++cnt].t=t;
	a1[cnt].n=h1[f];
	h1[f]=cnt;
}
void add2(int f,int t)
{
	a2[++cnt].t=t;
	a2[cnt].n=h2[f];
	h2[f]=cnt;
}
void spfa1(int s) 
{
	queue<int> q;
	memset(f1,0x3f,sizeof f1);
	memset(b,0,sizeof b);
	b[s]=1;
	q.push(s);
	while(!q.empty())
	{
		int u=q.front();
		q.pop();b[u]=0;
		f1[u]=min(f1[u],j[u]);
		for(int i=h1[u];i;i=a1[i].n)
		{
			int to=a1[i].t;
			if(f1[to]>f1[u])
			{
				f1[to]=f1[u];
				if(!b[to]) b[to]=1,q.push(to);
			}
		}
	}
}
void spfa2(int s) 
{
	queue<int> q;
	memset(b,0,sizeof b);
	b[s]=1;
	q.push(s);
	while(!q.empty())
	{
		int u=q.front();
		q.pop();b[u]=0;
		f2[u]=max(f2[u],j[u]);
		for(int i=h2[u];i;i=a2[i].n)
		{
			int to=a2[i].t;
			if(f2[to]<f2[u])
			{
				f2[to]=f2[u];
				if(!b[to]) b[to]=1,q.push(to);
			}
		}
	}
}
int main()
{
    cin>>n>>m;
    for(int i=1;i<=n;i++) cin>>j[i];
    for(int i=1;i<=m;i++)
	{
		int x,y,w;
		cin>>x>>y>>w;
		add1(x,y),add2(y,x);
		if(w==2) add1(y,x),add2(x,y);
	}
	spfa1(1);
	spfa2(n);
	for(int i=1;i<=n;i++) ans=max(ans,f2[i]-f1[i]);
	cout<<ans;
    return 0;
}

周星宇

周星宇