记录编号	597050	评测结果	AAAAAAAAAA
题目名称	[NOIP 2009]最优贸易	最终得分	100
用户昵称	lihaoze	是否通过	通过
代码语言	C++	运行时间	0.757 s
提交时间	2024-11-20 20:44:07	内存使用	7.35 MiB

#include "bits/stdc++.h"

using i64 = long long;

constexpr int INF = 0x3f3f3f3f;

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

    freopen("trade.in", "r", stdin);
    freopen("trade.out", "w", stdout);

    int n, m;
    std::cin >> n >> m;

    std::vector<int> a(n + 1);
    for (int i = 1; i <= n; ++ i) {
        std::cin >> a[i];
    }

    std::map<int, std::vector<int>> adj, inv;
    for (int i = 1; i <= m; ++ i) {
        int a, b, t;
        std::cin >> a >> b >> t;

        adj[a].push_back(b);
        inv[b].push_back(a);

        if (t == 2) {
            adj[b].push_back(a);
            inv[a].push_back(b);
        }
    }

    std::vector<int> min(n + 1, INF), max(n + 1, 0);

    auto spfa = [&] () {
        std::bitset<100010> st;

        do {
            std::queue<int> q;
            q.push(1), st[1] = true;

            min[1] = a[1];

            while (q.size()) {
                int u = q.front();
                q.pop(), st[u] = false;

                for (auto &v : adj[u]) {
                    if (min[v] > std::min(min[u], a[v])) {
                        min[v] = std::min(min[u], a[v]);

                        if (!st[v]) {
                            q.push(v), st[v] = true;
                        }
                    }
                }
            }
        } while (false);

        do {
            std::queue<int> q;
            q.push(n), st[n] = true;

            max[n] = a[n];

            while (q.size()) {
                int u = q.front();
                q.pop(), st[u] = false;

                for (auto &v : inv[u]) {
                    if (max[v] < std::max(max[u], a[v])) {
                        max[v] = std::max(max[u], a[v]);

                        if (!st[v]) {
                            q.push(v), st[v] = true;
                        }
                    }
                }
            }
        } while (false);
    };

    spfa();

    int res = 0;
    for (int i = 1; i <= n; ++ i) {
        res = std::max(res, max[i] - min[i]);
    }

    std::cout << res << '\n';

    return 0;
}