wa16分求解

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

elpsconr @ 2024-04-08 01:34:24

wa了四个点,只有样例和第四个数据过了,不知如何修改求解。

#include<bits/stdc++.h>
using namespace std;
#define PII pair<int,int>
const int N=2e5+6;
int n,m,s,idx;
int e[N<<1],h[N],w[N<<1],ans[N],ne[N<<1];
bool st[N];
void add(int a,int b,int c)
{
    e[idx]=b;w[idx]=c;ne[idx]=h[a];h[a]=idx++;
}
void bfs(int x)
{
    queue<PII> q;
    st[x]=1;q.push({0,x});
    while(!q.empty())
    {
        int ww=q.front().second;q.pop();
        for(int i=h[ww];~i;i=ne[i])
        {
            int j=e[i];
            if(j==ww) continue;
            ans[j]=ans[ww]+w[i];
            if(!st[j]) st[j]=1,q.push({ans[j],j});
        }
    }
}
int main()
{
    memset(ans,0x3f,sizeof ans);
    memset(st,0,sizeof st);
    memset(h,-1,sizeof h);
    cin>>n>>m>>s;
    ans[s]=0;
    for(int i=1;i<=m;++i)
    {
       int u,v,r;cin>>u>>v>>r;
       add(u,v,r);
    }
    bfs(s);
    for(int i=1;i<=n;++i)
    cout<<ans[i]<<" ";
    return 0;
}

|