请求帮助!
查看原帖
请求帮助!
724221
ILoveSoviet楼主2023/4/29 15:29

下面这个代码好像和老师写的一模一样,但是只能拿到最后一个数据点:

#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]<<" ";
    }
}

请帮我看一看,谢谢!

2023/4/29 15:29
加载中...