题解 P3371 【【模板】单源最短路径（弱化版）】

Orichalcos · 2019-04-27 18:43:08 · 题解

大佬都在用SPFA，本蒟蒻只好写个dijkstra算法玩玩. 1927ms.

#include<bits/stdc++.h>
using namespace std;
const int maxn=500013;
struct Edge{
    Edge(){
        v=0;
        w=0;
    }
    Edge(int _v,int _w){
        v=_v;
        w=_w;
    }
    int v,w;
};
vector<Edge> G[maxn];
int n,m;
int d[maxn];//从起始点到其它点最短距离
int vis[maxn];
void dijkstra(int s){
    const int inf=0x7fffffff;//2^32 -1
    for(int i=1;i<=n;i++){
        d[i]=inf;
    }
    d[s]=0;
    for(int q=1;q<=n;q++){
        // step1
        // find min_ and minindex
        int min_=0x7fffffff;
        int minindex=0;
        for(int i = 1; i <= n; i++) {
            if(d[i] < min_ && vis[i] == 0) {
                min_ = d[i];
                minindex = i;
            }
        }
        vis[minindex] = 1;
        // end of step 1
        // step2
        // use minindex to update array d[]
        for(int i=0;i<G[minindex].size();i++){
            Edge e=G[minindex][i];
            if(d[e.v]>d[minindex]+e.w){
                d[e.v]=d[minindex]+e.w;
            }
        }
        // end of step2
    }

}

int main(){
    int s;
    cin>>n>>m>>s;
    for(int i=1;i<=m;i++){
        int u,v,w;
        cin>>u>>v>>w;
        Edge temp1(v,w);
        G[u].push_back(temp1);
    }
    dijkstra(s);
    for(int i=1;i<=n;i++){
        cout<<d[i]<<' ';
    }
    cout<<endl;
}