python/TangDou/AcWing_TiGao/T3/MiniPathYingYong/341.cpp

#include <bits/stdc++.h>
using namespace std;
typedef pair<int, int> PII;
const int INF = 0x3f3f3f3f;
const int N = 100010, M = 2000010;

int n, m;
int dis1[N], dis2[N];

// 正反建图，传入头数组指针
int h1[N], h2[N], e[M], ne[M], w[M], idx;
void add(int *h, int a, int b, int c = 0) {
    e[idx] = b, ne[idx] = h[a], w[idx] = c, h[a] = idx++;
}

// 每个节点的价值
int v[N];

void dijkstra1() {
    memset(dis1, 0x3f, sizeof dis1);
    priority_queue<PII, vector<PII>, greater<PII>> q;
    dis1[1] = v[1];
    q.push({dis1[1], 1});

    while (q.size()) {
        int u = q.top().second;
        q.pop();

        for (int i = h1[u]; ~i; i = ne[i]) {
            int j = e[i];
            if (dis1[j] > min(dis1[u], v[j])) {
                dis1[j] = min(dis1[u], v[j]);
                q.push({dis1[j], j});
            }
        }
    }
}

void dijkstra2() {
    memset(dis2, -0x3f, sizeof dis2);
    priority_queue<PII> q;
    dis2[n] = v[n];
    q.push({dis2[n], n});

    while (q.size()) {
        int u = q.top().second;
        q.pop();
        
        for (int i = h2[u]; ~i; i = ne[i]) {
            int j = e[i];
            if (dis2[j] < max(dis2[u], v[j])) {
                dis2[j] = max(dis2[u], v[j]);
                q.push({dis2[j], j});
            }
        }
    }
}

int main() {
    // 正反两张图
    //  Q:为什么要反着建图，用正着的图不行吗？
    //  A:不行啊，因为从n向其它地方走，原来的有向图无法向对面走啊，反着建图就行了
    memset(h1, -1, sizeof h1);
    memset(h2, -1, sizeof h2);

    scanf("%d %d", &n, &m);                          // n个节点，m条边
    for (int i = 1; i <= n; i++) scanf("%d", &v[i]); // 每个节点购买水晶球的金额

    while (m--) {
        int a, b, c;
        scanf("%d %d %d", &a, &b, &c);
        // 不管是单向边，还是双向边，第一条a->b的边肯定跑不了吧

        if (c == 1) { // 单向边
            // 正向图保存单向边
            add(h1, a, b);
            // 反向图保存单向边
            add(h2, b, a);
            // 注意：这可不是在一个图中创建两条来回的边，而是在两个图中创建两个相反的边。
            // 权值呢？没有，为什么呢？因为我们不关心边权，而是关心此节点中水晶球的价格v[i]，这并不是边权,可以理解为点权
        } else { // 双向边
            // 正向图保存双向边
            add(h1, a, b), add(h1, b, a);
            // 反向图保存双向边
            add(h2, a, b), add(h2, b, a);
        }
    }
    // 正向图跑一遍dijkstra
    dijkstra1();

    // 反向图跑一遍dijkstra
    dijkstra2();

    int ans = 0;
    for (int i = 1; i <= n; i++)
        ans = max(dis2[i] - dis1[i], ans);

    printf("%d\n", ans);
    return 0;
}