求解20分8WA SPFA

#include #include #include using namespace std; int n,m; int val[100001],book[100001]; struct note { int num=-99999;//num表示到当前点的差值最大 int minn=99999;//minn表示到当前点路径上val的最小值 } dis[100001]; vector a[100001]; queue q; void add(int x,int y) { a[x].push_back(y); return ; } int main() { cin>>n>>m; int x,y,k; for(int i=1; i<=n; i++) { cin>>val[i]; } for(int i=1; i<=m; i++) { cin>>x>>y>>k; if(k==1) { add(x,y); } else { add(x,y); add(y,x); } } /for(int i=1; i<=n; i++) { for(int j=0; j<a[i].size(); j++) { cout<<a[i][j]<<" "; } cout<<endl; }/ q.push(1); dis[1].num=0; book[1]=1; for(int i=1; i<=n; i++) { dis[i].minn=val[i]; } while(!q.empty()) { int t=q.front(); for(int k=0; k<a[t].size(); k++) { int to=a[t][k]; //更新最小值 if(dis[to].minn>dis[t].minn) { dis[to].minn=dis[t].minn; if(book[to]==0){ q.push(to); book[to]=1; } } //更新差值 if(dis[to].num<val[to]-dis[to].minn) { dis[to].num=val[to]-dis[to].minn; if(book[to]==0) { q.push(to); book[to]=1; } } } book[q.front()]=0; q.pop(); } int maxn=-99999; for(int i=1; i<=n; i++) { maxn=max(maxn,dis[i].num); //cout<<dis[i].num<<" "; } //cout<<endl; cout<<maxn; return 0; }