下面这个代码好像和老师写的一模一样,但是只能拿到最后一个数据点:
#include<iostream>
#include<queue>
#define mm 500010
using namespace std;
int head[mm],m,n,s,cnt,dis[mm],vis[mm],fq[mm];
struct node{
int u,v,w,bef;
}edge[mm];
queue<int> q;
void add(int u,int v,int w){
cnt++;
edge[cnt].u=u;
edge[cnt].v=v;
edge[cnt].w=w;
edge[cnt].bef=head[u];
head[u]=cnt;
}
bool have_answer=1;
void spaf(){
q.push(s);
while(!q.empty()){
int uw=q.front();
q.pop();
vis[uw]=0;
for(int i=head[uw];i;i=edge[i].bef){
int v=edge[i].v;
int u=uw;
if(dis[v]>dis[u]+edge[i].w){
dis[v]=dis[u]+edge[i].w;
fq[v]=fq[u]+1;
if(fq[v]>m) {cout<<"NO";have_answer=0;return;}
if(vis[i]==0){
vis[i]=1;
q.push(v);
}
}
}
}
}
int main(){
ios_base::sync_with_stdio(false);
cin>>m>>n;
s=0;
for(int i=0;i<n;i++){
int u,v,w;
cin>>u>>v>>w;
add(v,u,w);
}
for(int i=1;i<=m;i++){
dis[i]=((1<<31)-1);
add(0,i,mm);
}
dis[s]=0;
vis[s]=1;
spaf();
if(have_answer==0) return 0;
for(int i=1;i<=m;i++){
cout<<dis[i]<<" ";
}
}
请帮我看一看,谢谢!