dik

本文主要是介绍dik，对大家解决编程问题具有一定的参考价值，需要的程序猿们随着小编来一起学习吧！

#include<bits/stdc++.h>

using namespace std;

const int N = 200000,Inf=0x7fffff;

struct edge{
    int u,v,w;
    edge(int a,int b,int c){
        u=a,v=b,w=c;
    }
};
vector<edge> e[N];

struct node{
    int id,dis;
    node(int a,int b){id=a,dis=b;}
    inline bool operator <(const node& a)const{
        return dis>a.dis;
    }
};
int pre[N],n,m;

void dijkstra(int s) {
    int dis[N];
    bool f[N];
    for (int i = 0; i <= n; i++) {
        dis[i] = Inf, f[i] = false;
    }
    dis[s] = 0;
    priority_queue<node> q;
    q.push(node(s, 0));
    while (!q.empty()) {
        node u = q.top();
        q.pop();
        if (f[u.id]) continue;
        f[u.id] = true;
        for (int i = 0; i < e[u.id].size(); i++) {
            auto tp = e[u.id][i];
            if (f[tp.v]) continue;
            if (dis[tp.v] > tp.w + u.dis) {
                dis[tp.v] = tp.w + u.dis;
                q.push(node(tp.v, dis[tp.v]));
                //
            }
        }
    }
    // cout<<dis[s]<<endl;
    for (int i = 1; i <= n; i++) {
        cout << dis[i] << endl;
    }
}



int main(){
    ios::sync_with_stdio(false);
    int s,u,v,w;
    cin>>n>>m>>s;
    for (int i = 1; i <= m; i++) {
        int a,b,c;
        cin>>a>>b>>c;
        e[a].push_back(edge(a,b,c));
        e[b].push_back(edge(b,a,c));
    }
    dijkstra(s);

    return 0;
}

这篇关于dik的文章就介绍到这儿，希望我们推荐的文章对大家有所帮助，也希望大家多多支持为之网！