HangingKill
#include<cstdio>
#include<queue>
#include<cstring>
#include<algorithm>
#include<cmath>
using namespace std;
const int MAXN = 10001, inf = 0x3f3f3f3f,No_Road=pow(2,31)-1;
#define scanf scanf_s
class Dijkstra {
private:
    int fi[MAXN], to[MAXN], ne[MAXN], w[MAXN], tot;
    int dis[MAXN];
    int m, n, s;
    bool vis[MAXN];
    inline void link(int u, int v, int tw) {
        tot++;
        to[tot] = v;
        ne[tot] = fi[u];
        w[tot] = tw;
        fi[u] = tot;
    }    
    inline void init() {
        tot = 0;
        scanf("%d%d%d", &n, &m, &s);
        int t1, t2, t3;
        for (int i = 1; i <= m; i++) {
            scanf("%d%d%d", &t1, &t2, &t3);
            link(t1, t2, t3);
        }
        memset(dis, inf, sizeof(dis));
    }
    inline void dijkstra() {
        dis[s] = 0;
        for (int i = 1; i <= n; i++) {
            int low = inf,ldis=inf;
            for (int j = 1; j <= n; j++) {
                if (dis[j] < ldis && !vis[j]) {
                    low = j;
                    ldis = dis[j];
                }
            }
            if (ldis == inf)return;
            vis[low] = 1;
            for (int j = fi[low]; j!=0; j = ne[j]) {
                if (!vis[to[j]] && dis[to[j]] > ldis + w[j])dis[to[j]] = ldis + w[j];
            }
        }
    }
public:
    inline void work() {
        init();
        dijkstra();
        for (int i = 1; i <= n; i++) {
            printf("%d ",dis[i]);
        }
    }
};
#undef scanf
除非特别注明,本页内容采用以下授权方式: Creative Commons Attribution-ShareAlike 3.0 License