MCOI Round 2 D 题题解

· · 个人记录

刚才催了一下管理，回复：

最近很多比赛管理都开学了，很抱歉审核速度降低
不过已转告给相关管理

ohhhhhhhhhhhhhh!

所有来写一下 D 题题解。

Subtask 1

让你输出样例你就输出呗。

Subtask 2

A+B

Subtask 3

求 s 到 t 的最短路，SPFA 解决。

Subtask 4

求 s 到 t 的最短路，纯 SPFA 会超时，SPFA + deque 优化可过。

Code

你还 ……

算了给一个 Sub 3 的代码吧！

#include <bits/stdc++.h>

using namespace std;

struct node {
    int val, next, length;
} e[200086];

const int inf = 0x3f3f3f3f;

int n, m, s, cnt;
int head[100086];
int dist[100086], sum[100086];

void AddEdge (int u, int v, int w) {
    e[++cnt].val = v;
    e[cnt].next = head[u];
    e[cnt].length = w;
    head[u] = cnt;
}

struct cmp {
    bool operator () (int a, int b) {
        return dist[a] > dist[b];
    }
};

priority_queue <int, vector<int>, cmp> q;

int main () {
    scanf("%d%d%d", &n, &m, &s);
    for (int i = 1, u, v, w; i <= m; i++) {
        scanf("%d%d%d", &u, &v, &w);
        AddEdge(u, v, w);
    }
    for (int i = 1; i <= n; i++)
        dist[i] = inf;
    dist[s] = 0;
    sum[s] = 1;
    q.push(s);
    while (!q.empty()) {
        int cur = q.top();
        q.pop();
        sum[cur] = 0;
        for (int p = head[cur]; p > 0; p = e[p].next)
            if (dist[e[p].val] > dist[cur] + e[p].length) {
                dist[e[p].val] = dist[cur] + e[p].length;
                if (!sum[e[p].val]) {
                    q.push(e[p].val);
                    sum[e[p].val] = 1;
                }
            }
    }
    for (int i = 1; i <= n; i++)
        printf("%d ", dist[i]);
    return 0;
}