求大佬找错

#include<iostream>
#include<cstdio>
#include<cstring>
#include<cstdlib>
#include<vector>
#include<queue>
#include<vector>
using namespace std;
int inf=0x7fffffff;
int ans,vis[200000],a[200000],b[200000],pri[200000],n,m;
vector<int>cn[200000],ccn[200000];
void spfa1()
{
queue<int>q;
q.push(1);
memset(a,inf,sizeof(a));
memset(vis,0,sizeof(vis));
vis[1]=1;
while (!q.empty())
{
int x=q.front();
q.pop();
a[x]=min(a[x],pri[x]);
for (int i=0;i<cn[x].size();i++)
{
int v=cn[x][i];
if (a[x]<a[v])
{
a[v]=a[x];
if (!vis[v])
{
vis[v]=1;
q.push(v);
}
}
}
vis[x]=0;
}
}
void spfa2()
{
queue<int>q;
q.push(n);
memset(vis,0,sizeof(vis));
memset(b,0,sizeof(b));
vis[n]=1;
while (!q.empty())
{
int x=q.front();
q.pop();
b[x]=max(b[x],pri[x]);
for (int i=0;i<ccn[x].size();i++)
{
int v=ccn[x][i];
if (b[x]>b[v])
{
b[v]=b[x];
if (!vis[v])
{
vis[v]=1;
q.push(v);
}
}
}
vis[x]=0;
}
}
int main()
{
cin>>n>>m;
for (int i=1;i<=n;i++)
cin>>pri[i];
int x,y,k;
for (int i=1;i<=m;i++)
{
cin>>x>>y>>k;
cn[x].push_back(y);
ccn[y].push_back(x);
if (k>1)
{
cn[y].push_back(x);
ccn[x].push_back(y);
}
}
spfa1();spfa2();
for (int i=1;i<=n;i++)
{
ans=max(ans,b[i]-a[i]);
}
cout<<ans;
return 0;
}

0 条评论

目前还没有评论...

信息

ID
1754
难度
6
分类
图结构 | 最短路 点击显示
标签
递交数
2626
已通过
654
通过率
25%
上传者