样例都过不了,求助

P4779 【模板】单源最短路径(标准版)

Forose @ 2023-12-24 10:56:38

#include<cstdio>
#include<queue>
using namespace std;
const int N=2e5+10; 
int n,m,s;
long long ans[N];
int vis[N],head[N],cnt; 
struct edge{
    int to,next,dis;//to:儿子 next:兄弟 dis:权值 
}kun[N];
struct node{
    int ans,id;//ans值  点的编号 
    bool operator <(const node &x)const
    {
        return x.ans<ans;
    }//要背 重载运算符 
};
void add(int u,int v,int d){//起点 终点 权值 
    cnt++;
    kun[cnt].next=head[u];//确定兄弟 
    kun[cnt].to=v;//终点 
    kun[cnt].dis=d; //权值 
    head[u]=cnt; //更新 
} //存图 
priority_queue<node> q; //堆
void Dijstra(){
    ans[s]=0;
    q.push( (node) {0,s});//node为强转 
    for(int i=0;i<N;i++) ans[i]=1e9;//初始化 
    while(!q.empty()){
        node hp=q.top();
        q.pop();
        int idn=hp.id,ansn=hp.ans;
        if(vis[idn]==0){//如果未访问过 
            vis[idn]=1;//标记 
            for(int i=head[idn];i!=0;i=kun[i].next){//枚举 
                int ypy=kun[i].to;
                if(ans[idn]+kun[i].dis<ans[ypy]){//松弛操作 
                    ans[ypy]=ans[idn]+kun[i].dis;
                    if(vis[ypy]==0){
                        q.push( (node){ans[ypy],ypy});
                    }
                }
            }
        }
    }
} 
int main(){
    scanf("%d %d %d",&n,&m,&s);
    for(int i=1;i<=m;i++){
        int a,b,c;
        scanf("%d %d %d",&a,&b,&c);
        add(a,b,c);
    }
    Dijstra();
    for(int i=1;i<=n;i++){
        printf("%d ",ans[i]);
    }
    return 0;
} 

by __ZTY__ @ 2023-12-24 15:34:36

ans[s]=0;
q.push( (node) {0,s});//node为强转 
for(int i=0;i<N;i++) ans[i]=1e9;//初始化 

初始化把ans的值覆盖了


|