洛谷 P1073 [NOIP 2009 提高组] 最优贸易

// P1073 [NOIP 2009 提高组] 最优贸易 —— ★ 这一版就能 AC（分层图 + 本章的 Dijkstra）
//
// 题目要的是：从 1 走到 n（点可以重复经过），中途选一个城市买、之后某个城市卖，
// 让「卖价 − 买价」最大。
//
// ★ 关键的一步分两半。
//
// 【一】**状态是「走到哪儿」＋「贸易做到哪一步」** ⇒ 把图复制成三层：
//        第 0 层 = 还没买      第 1 层 = 买了还没卖      第 2 层 = 已经卖了
//      · 层内：原图的边，边权 0（走路不花钱）；
//      · 第 0 层的 i → 第 1 层的 i：在 i 买入；
//      · 第 1 层的 i → 第 2 层的 i：在 i 卖出。
//      答案就是「从 (1, 第 0 层) 走到 (n, 第 2 层)」的最优值。
//
// 【二】★★★ 而这道题真正的机关是：**怎么把「求最大利润」变成非负权最短路。**
//      顺手的做法是买入 −p、卖出 +p 再求最长路 —— 那就**不是 Dijkstra 了**（有负权）。
//      换个记法：
//            买入那条边的权 =  p[i]          （0 ≤ p ≤ 100）
//            卖出那条边的权 =  100 − p[i]    （0 ≤ … ≤ 100）★ 也非负
//      于是一条完整路线的总权 = 买价 + (100 − 卖价) = **100 − 利润**。
//      ⇒ **最小化它就是最大化利润**，而所有边权都 ≥ 0 —— 本章的 Dijkstra 原样能用。
//
//   ★ 那个 100 是从哪儿来的？题面最后一行：「**水晶球价格 ≤ 100**」。
//     ⇒ 又一次「题面上那几行数字，每一行都是一件工具」——
//       这一行不是背景，它是**让这道题落进 Dijkstra 射程**的那把钥匙。
//
// ⚠ 「不做贸易」也是允许的：在同一个城市买了立刻卖，利润 0；
//   分层图里就是 i 的三层顺着走一遍，权 = p + (100 − p) = 100 ⇒ 利润 0。所以答案天然 ≥ 0。
//
// 复杂度 O(3m log(3n))：顶格 n = 10⁵、m ≈ 5×10⁵ ⇒ 本机 0.28 秒（时限 1 秒；
//   而正反两遍那版 0.14 秒 —— 分层图的代价是常数 3，换来的是「状态」这件事说得清）。

#include <bits/stdc++.h>
using namespace std;
typedef pair<int, int> PII;

const int INF = 0x3f3f3f3f;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int n, m;
    if (!(cin >> n >> m)) return 0;
    vector<int> p(n + 1);
    for (int i = 1; i <= n; i++) cin >> p[i];

    int N = 3 * n;                                  // 三层，(层, 点) 编号成 层*n + 点
    auto id = [&](int layer, int v) { return layer * n + v; };
    vector<vector<PII>> g(N + 1);
    for (int i = 0; i < m; i++) {
        int x, y, z;
        cin >> x >> y >> z;
        for (int L = 0; L < 3; L++) {               // 三层里各连一遍，边权 0
            g[id(L, x)].push_back({id(L, y), 0});
            if (z == 2) g[id(L, y)].push_back({id(L, x), 0});
        }
    }
    for (int v = 1; v <= n; v++) {
        g[id(0, v)].push_back({id(1, v), p[v]});          // ★ 买入：花 p[v]
        g[id(1, v)].push_back({id(2, v), 100 - p[v]});    // ★ 卖出：花 100 − p[v]
    }

    vector<int> dist(N + 1, INF);
    priority_queue<PII, vector<PII>, greater<PII>> q;
    int s = id(0, 1);
    dist[s] = 0;
    q.push({0, s});
    while (!q.empty()) {
        auto [d, u] = q.top();
        q.pop();
        if (d > dist[u]) continue;
        for (auto [v, w] : g[u])
            if (d + w < dist[v]) { dist[v] = d + w; q.push({dist[v], v}); }
    }
    int t = dist[id(2, n)];
    cout << (t >= INF ? 0 : 100 - t) << '\n';
    return 0;
}

// ✗ 错法①：正反两遍是对的，可**用 Dijkstra 的贪心去做它**（弹出即定死）
//
// ★★★ 这是这一页最值钱的一条：**Dijkstra 的骨架不是随便能套的。**
//
//   本章第 5 步那三句反证，靠的是一句话：
//   「那条路走到 x 之后还要往前走，而**往前走只会更长**（边长非负）。」
//   ⇒ 所以「当前最小的那个」不可能再被刷小，可以当场定死。
//
//   而这道题的 minBuy 是「路上的**最低价**」—— **往前多走一步只会让它更小**。
//   那个单调性**正好反过来了** ⇒ 弹出即定死的理由整个不成立。
//
// ⚠ 最小反例只要 4 个点（度量程序第 ③ 段真跑了一遍）：
//     价格 10 8 1 7，边 1 → 2、2 → 3、3 → 4、1 → 4
//     · 真正的 minBuy[4] = 1（走 1 → 2 → 3 → 4）
//     · 贪心：弹出 1（10）⇒ 4 的暂定值 min(10, 7) = 7、2 的暂定值 8
//       ⇒ 堆顶是 (7, 4)，**4 号被带着 7 定死了**，而 3 号（价 1）还没轮到。
//
// ⚠⚠ 而「minBuy 算错了」推不出「**答案**一定错」—— 这两件事这一页分开量了（正文第 ③ 步）。

#include <bits/stdc++.h>
using namespace std;
typedef pair<int, int> PII;

int main(int argc, char** argv) {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    bool showMin = (argc > 1 && string(argv[1]) == "minbuy");   // 只打 minBuy[]，给反例用

    int n, m;
    if (!(cin >> n >> m)) return 0;
    vector<int> p(n + 1);
    for (int i = 1; i <= n; i++) cin >> p[i];
    vector<vector<int>> g(n + 1), rg(n + 1);
    for (int i = 0; i < m; i++) {
        int x, y, z;
        cin >> x >> y >> z;
        g[x].push_back(y);
        rg[y].push_back(x);
        if (z == 2) { g[y].push_back(x); rg[x].push_back(y); }
    }

    const int INF = 0x3f3f3f3f;
    /* ⚠ 小根堆 + 「弹出即定死」—— 照搬 Dijkstra 的骨架 */
    vector<int> mn(n + 1, INF), done(n + 1, 0);
    priority_queue<PII, vector<PII>, greater<PII>> q;
    mn[1] = p[1];
    q.push({mn[1], 1});
    while (!q.empty()) {
        auto [d, u] = q.top();
        q.pop();
        if (done[u]) continue;
        done[u] = 1;                                 // ⚠ 就是这一句：定死了就不许再改
        for (int v : g[u]) {
            int cand = min(d, p[v]);
            if (!done[v] && cand < mn[v]) { mn[v] = cand; q.push({cand, v}); }
        }
    }
    if (showMin) {
        for (int i = 1; i <= n; i++) printf("%d%c", mn[i] >= INF ? -1 : mn[i], " \n"[i == n]);
        return 0;
    }
    /* 反着那一遍同样用大根堆 + 弹出即定死 */
    vector<int> mx(n + 1, -1), done2(n + 1, 0);
    priority_queue<PII> q2;
    mx[n] = p[n];
    q2.push({mx[n], n});
    while (!q2.empty()) {
        auto [d, u] = q2.top();
        q2.pop();
        if (done2[u]) continue;
        done2[u] = 1;
        for (int v : rg[u]) {
            int cand = max(d, p[v]);
            if (!done2[v] && cand > mx[v]) { mx[v] = cand; q2.push({cand, v}); }
        }
    }
    int ans = 0;
    for (int v = 1; v <= n; v++)
        if (mn[v] < INF && mx[v] >= 0) ans = max(ans, mx[v] - mn[v]);
    cout << ans << '\n';
    return 0;
}

// ✗ 错法②：假设这张图**无环**，按拓扑序做一遍 DP
//
// 想法很自然：从 1 出发的路线是「一步一步往前走」，那就按拓扑序推
//     minBuy[v] = min(p[v], min over u→v of minBuy[u])
// 一遍扫完，`O(n + m)`，比什么都快。
//
// ⚠ 而题面里那一行就是冲着它写的：
//   「**对于 50% 的数据，不存在一条旅游路线，可以从一个城市出发，再回到这个城市。**」
//   —— 出题人明说了：**有一半的数据是 DAG**。这一版稳拿 50 分。
//   ⇒ 又一次「[题面的数据范围分档是出题人递过来的工具](/sol/p1141/)」：
//     那一档不是提示，是**给这个写法留的分**。
//
// ⚠ 而题面样例里就有环（`2 3 2` 和 `4 5 2` 都是双向的，双向边本身就是一个二元环）
//   ⇒ 环上的点进不了拓扑序，这一版直接把它们当成走不到。
//
// ★ 方向可判：它**少算**了一批路线 ⇒ 利润只会更小 ⇒ **答案恒 ≤ 正解**。

#include <bits/stdc++.h>
using namespace std;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int n, m;
    if (!(cin >> n >> m)) return 0;
    vector<int> p(n + 1);
    for (int i = 1; i <= n; i++) cin >> p[i];
    vector<vector<int>> g(n + 1), rg(n + 1);
    vector<int> deg(n + 1, 0), rdeg(n + 1, 0);
    for (int i = 0; i < m; i++) {
        int x, y, z;
        cin >> x >> y >> z;
        g[x].push_back(y); rg[y].push_back(x); deg[y]++; rdeg[x]++;
        if (z == 2) { g[y].push_back(x); rg[x].push_back(y); deg[x]++; rdeg[y]++; }
    }

    const int INF = 0x3f3f3f3f;
    vector<int> mn(n + 1, INF), mx(n + 1, -1);
    mn[1] = p[1];
    {                                                // ⚠ 正着一遍拓扑序
        queue<int> q;
        for (int i = 1; i <= n; i++) if (!deg[i]) q.push(i);
        while (!q.empty()) {
            int u = q.front(); q.pop();
            for (int v : g[u]) {
                if (mn[u] < INF) mn[v] = min(mn[v], min(mn[u], p[v]));
                if (--deg[v] == 0) q.push(v);
            }
        }
    }
    mx[n] = p[n];
    {                                                // ⚠ 反着一遍拓扑序
        queue<int> q;
        for (int i = 1; i <= n; i++) if (!rdeg[i]) q.push(i);
        while (!q.empty()) {
            int u = q.front(); q.pop();
            for (int v : rg[u]) {
                if (mx[u] >= 0) mx[v] = max(mx[v], max(mx[u], p[v]));
                if (--rdeg[v] == 0) q.push(v);
            }
        }
    }
    int ans = 0;
    for (int v = 1; v <= n; v++)
        if (mn[v] < INF && mx[v] >= 0) ans = max(ans, mx[v] - mn[v]);
    cout << ans << '\n';
    return 0;
}

// ✗ 错法③：`z = 2` 那些**双向**道路，只当成 x → y 一个方向
//
// 题面：「如果 `z = 1`，表示这条道路是城市 x 到城市 y 的单向道路；
//        如果 `z = 2`，表示这条道路为城市 x 和城市 y 之间的**双向**道路。」
//
// ⇒ ★★★ 「存一遍还是两遍」在这一章的题单里出现了**第四次**，而且这次是**同一张输入里两种都有**：
//     [P1339](/sol/p1339/) 全无向 —— 必须存两遍；
//     [P1629](/sol/p1629/) 全单向 —— 存两遍就错；
//     [P1462](/sol/p1462/) 全双向 —— 又必须存两遍；
//     P1073（这道题）—— ★ **同一行输入里，`z` 说了算。**
//
// ★ 方向可判：边少了 ⇒ 路线只会更少 ⇒ **答案恒 ≤ 正解**。
// ⚠ 而它在「全是单向边」那一档上是**结构性的 0**（那一档根本没有 z = 2）。

#include <bits/stdc++.h>
using namespace std;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int n, m;
    if (!(cin >> n >> m)) return 0;
    vector<int> p(n + 1);
    for (int i = 1; i <= n; i++) cin >> p[i];
    vector<vector<int>> g(n + 1), rg(n + 1);
    for (int i = 0; i < m; i++) {
        int x, y, z;
        cin >> x >> y >> z;
        g[x].push_back(y);
        rg[y].push_back(x);
        (void)z;                                     // ⚠ z 读进来了，但没人用它
    }

    const int INF = 0x3f3f3f3f;
    vector<int> mn(n + 1, INF), mx(n + 1, -1);
    vector<char> inq(n + 1, 0);
    deque<int> q;
    mn[1] = p[1]; q.push_back(1); inq[1] = 1;
    while (!q.empty()) {
        int u = q.front(); q.pop_front(); inq[u] = 0;
        for (int v : g[u]) {
            int cand = min(mn[u], p[v]);
            if (cand < mn[v]) { mn[v] = cand; if (!inq[v]) { inq[v] = 1; q.push_back(v); } }
        }
    }
    fill(inq.begin(), inq.end(), 0);
    mx[n] = p[n]; q.push_back(n); inq[n] = 1;
    while (!q.empty()) {
        int u = q.front(); q.pop_front(); inq[u] = 0;
        for (int v : rg[u]) {
            int cand = max(mx[u], p[v]);
            if (cand > mx[v]) { mx[v] = cand; if (!inq[v]) { inq[v] = 1; q.push_back(v); } }
        }
    }
    int ans = 0;
    for (int v = 1; v <= n; v++)
        if (mn[v] < INF && mx[v] >= 0) ans = max(ans, mx[v] - mn[v]);
    cout << ans << '\n';
    return 0;
}