【题解】洛谷P4799【模板】单源最短路径（标准版） dijkstra

题目链接

输入输出样例

输入样例#1：
4 6 1
1 2 2
2 3 2
2 4 1
1 3 5
3 4 3
1 4 4
输出样例#1：
0 2 4 3

---

#include<cstdio>
#include<vector>
#include<queue>
#include<algorithm>
#include<cstring>
#include<limits.h>
using namespace std;
struct edge{
    int v,cost;
    edge(int _v=0,int _cost=0):v(_v),cost(_cost){}
};
struct node{
    int v,c;
    node(int _v=0,int _c=0):v(_v),c(_c){}
    bool operator < (const node&r)const{
    return c>r.c;}
};
const int N=2e5+10;
int dist[N];
bool vis[N];
vector<edge>vx[N];
int n,m,s;
void dijkstra()
{
    memset(vis,0,sizeof(vis));
    priority_queue<node>q;
    while(!q.empty())q.pop();
    node tmp;
    dist[s]=0;
    q.push(node(s,0));
    while(!q.empty())
    {
        tmp=q.top();
        q.pop();
        int u=tmp.v;
        if(vis[u])continue;
        vis[u]=1;
        for(int i=0;i<vx[u].size();i++)
        {
            int v=vx[u][i].v;
            int cost=vx[u][i].cost;
            if(!vis[v]&&dist[v]>dist[u]+cost)
            {
                dist[v]=dist[u]+cost;
                q.push(node(v,dist[v]));
            }
        }
    }
}
int main()
{
    #ifdef local
    freopen("in.txt","r",stdin);
    #endif
    scanf("%d%d%d",&n,&m,&s);
    int u,v,w;
    for(int i=1;i<=m;i++)
    {
        scanf("%d%d%d",&u,&v,&w);
        vx[u].push_back(edge(v,w));
    }
    for(int i=0;i<=n;i++)
    dist[i]=INT_MAX;
    dijkstra();
    for(int i=1;i<=n;i++)printf("%d%c",dist[i],i==n?'\n':' ');
    return 0;
}

总结

关于SPFA：它死了