T? 求助大佬

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

hayoon @ 2023-11-12 09:29:23


#include<bits/stdc++.h>
using namespace std;
int head[200000];
long long dis[200000];
bool visit[200000];
int cnt=0;
struct edge
{
    int z;
    int val;
    int nexty;
}edge[1000000];
inline void add(int a,int b,int c)
{
    cnt++;
    edge[cnt].z=b;
    edge[cnt].val=c;
    edge[cnt].nexty=head[a];
    head[a]=cnt;
}
int main()
{
    int n,m,s;
    int a,b,c;
    scanf("%d%d%d",&n,&m,&s);
    for(int i=1;i<=n;i++)
    dis[i]=INT_MAX;
    for(int i=1;i<=m;i++)
    {
        scanf("%d%d%d",&a,&b,&c);
        add(a,b,c);
    }
    int curr=s;
    dis[s]=0;
    long long minn;
    while(!visit[curr])
    {
        visit[curr]=1;
        int i=head[curr];
        while(i!=0)
        {
            if(!visit[edge[i].z] && dis[edge[i].z]>dis[curr]+edge[i].val)
            dis[edge[i].z]=dis[curr]+edge[i].val;
            i=edge[i].nexty;
        }
        minn=INT_MAX;
        for(int i=1;i<=n;i++)
        {
            if(!visit[i]&&minn>dis[i])
            {
                minn=dis[i];
                curr=i;
            }
        }
    }
    for(int i=1;i<=n;i++)
    printf("%lld ",dis[i]);
    return 0;
}

真·不·理解

by wizard(偷开O2 @ 2023-11-12 09:59:02

1.建议改一下 visit 数组的名称 有歧义

2.你的代码弱化版能过,标准版数据很强,加 priority _ queue 优化


by wizard(偷开O2 @ 2023-11-12 09:59:20

@hayoon


|