求助大佬五颜六色的错误呜呜呜

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

BlinkSwiftie @ 2023-07-28 18:29:54

#include<bits/stdc++.h>
using namespace std;
const int N=1e5+3;
int head[N],nex[N],to[N],val[N],cnt;
int dis[N];
bool vis[N];
void addedge(int u,int v,int w)
{
    nex[++cnt]=head[u];
    head[u]=cnt;
    to[cnt]=v;
    val[cnt]=w;
} 
priority_queue<pair<int,int>,vector<pair<int,int> >,greater<pair<int,int> > > q;
int main()
{
    int n,m,x,y,z,s;
    scanf("%d%d%d",&n,&m,&s);
    for(int i=1;i<=m;++i)
    {
        scanf("%d%d%d",&x,&y,&z);
        addedge(x,y,z);
    }
    for(int i=1;i<=n;++i) dis[i]=0x3f3f3f3f;
    dis[s]=0;
    q.push(make_pair(0,s));
    while(!q.empty())
    {
        int x=q.top().second;
        q.pop();
        if(vis[x]) continue;
        vis[x]=1;
        for(int i=head[x];i;i=nex[i])
        {
            int v=to[i],length=val[i];
            if(dis[v]>dis[x]+length)
            {
                dis[v]=dis[x]+length;
                q.push(make_pair(dis[v],v));
            }
         } 
    }
    for(int i=1;i<=n;++i) cout<<dis[i]<<' ';
    return 0;
}

by Lien @ 2023-07-28 19:07:24

@BlinkSwiftie 你的部分数组越界,m\le2e5


|