HELP

#include<iostream>
#include<vector>
#include<queue>
#include<cstring>
using namespace std;
const int maxn=1001;
int flag=0;
int used[maxn],dist[maxn],in[maxn];
int n,m;
struct edge{
int to;
int v;
};
vector<edge> e[10001];
queue<int> q;
void spfa(int s){
dist[s]=0;
in[s]=1;
q.push(s);
while(!q.empty()){
int h=q.front();
in[h]=0;
used[h]++;
for(int i=0;i<e[h].size();i++){
if(dist[e[h][i].to]>dist[h]+e[h][i].v){
dist[e[h][i].to]=dist[h]+e[h][i].v;
if(!in[e[h][i].to]){
q.push(e[h][i].to);
in[e[h][i].to]=1;
}
}
}
q.pop();
in[h]=0;
}
if(dist[s]<0)flag=1;
}
int main(){
int op;
cin>>n>>m>>op;
int a,b,c;
edge p;
edge p1;
for(int i=1;i<=m;i++){
cin>>a>>b>>c;
p.to=b;p.v=c;
e[a].push_back(p);
}
for(int i=0;i<maxn;i++)dist[i]=99999999;
spfa(op);
for(int i=1;i<=n;i++){
if(!used[i]){
spfa(i);
}
}
if(flag==1)cout<<"-1";
else{
for(int i=1;i<=m;i++){
if(dist[i]>=99999999)cout<<"NoPath"<<endl;
else
cout<<dist[i]<<endl;
}
}
return 0;
}

哪不对
1,2,5,6没过

0 条评论

目前还没有评论...

信息

ID
1053
难度
8
分类
图结构 | 最短路 点击显示
标签
(无)
递交数
6945
已通过
594
通过率
9%
上传者