Dijkstra

HNOI前复习ing QAQ

/*
    Name: Dijkstra
    Author: Jack
    Date: 05/04/19 15:29
    Description:
      1.dist[start]=0,dist[1~n except start]=inf,sign[start]
      2.find x which is unmarked and dist[x]=min{dist[i]}
      3.scan the out edge of node x which is like (x,y,z),
        if(dist[y]>dist[x]+z) dist[y]=dist[x]+z
      4.do 2 and 3 until every node is marked
*/
#include<bits/stdc++.h>
using namespace std;
const int N=1e6+5,M=1e7+5;
const int inf=1e9;
struct edge{int y,z;};
vector<edge>e[N];
bool v[N];
int n,m,s,d[N];
priority_queue< pair<int,int> >q;
void add(int x,int y,int z){
    edge tmp1,tmp2;
    tmp1=(edge){y,z};e[x].push_back(tmp1);
}
void dij(int start){
    for(int i=1;i<=n;i++)d[i]=inf;
    memset (v,0,sizeof(v));
    d[start]=0;q.push(make_pair(0,s));
    while(q.size()){
        int x=q.top().second;q.pop();
        if(v[x])continue;v[x]=1;
        for(int i=0;i<e[x].size();i++){
            int y=e[x][i].y,z=e[x][i].z;
            if(d[y]>d[x]+z){
                d[y]=d[x]+z;
                q.push(make_pair(-d[y],y));
            }
        }
    }
    for(int i=1;i<=n;i++){
        printf("%d%c",d[i]==inf? 2147483647:d[i],i==n?'\n':' ');
    }
}
int main(){
    int x,y,z;
    scanf("%d%d%d",&n,&m,&s);
    for(int i=1;i<=m;i++){
        scanf("%d%d%d",&x,&y,&z);
        add(x,y,z);
    }
    dij(s);
    return 0;
}

Dijkstra

原文：https://www.cnblogs.com/yangxuejian/p/10759323.html