样例输入,结果输出0和两个无穷大数
啊啊,谁能救命啊啊
#include <bits/stdc++.h>
using namespace std;
struct Edge{
int to,dis,nxt;
}edge[5005];
int num_edge,n,m,u,v,w;
int head[5005],d[5005],visit[5005],cnt[5005];
void add_edge(int from,int to,int dis){
edge[++num_edge].nxt=head[from];
edge[num_edge].to=to;
edge[num_edge].dis=dis;
head[from]=num_edge;
}
bool spfa(){
queue<int> q;
q.push(1);
d[1]=0;cnt[1]++;visit[1]=1;
for(int i=2;i<=n;i++){
q.push(i);
visit[i]=1;
cnt[i]++;
}
while(!q.empty()){
int x=q.front();
q.pop();
visit[x]=0;
for(int i=head[x];i;i=edge[i].nxt){
int nto=edge[i].to,ndis=edge[i].dis;
if(d[nto]>d[x]+ndis){
d[nto]=d[x]+ndis;
if(!visit[nto]){
q.push(nto);
visit[nto]=1;
cnt[nto]++;
if(cnt[nto]>n)return false;
}
}
}
}
return true;
}
int main(){
memset(d,0x3f,sizeof(d));
cin>>n>>m;
for(int i=1;i<=m;i++){
cin>>u>>v>>w;
add_edge(v,u,w);
}
if(spfa()){
for(int i=1;i<=n;i++)
cout<<d[i]<<' ';
}else{
cout<<"NO"<<endl;
}
return 0;
}