记录编号	577225	评测结果	AAAAAAAAAA
题目名称	[NOIP 2009]最优贸易	最终得分	100
用户昵称	lihaoze	是否通过	通过
代码语言	C++	运行时间	0.902 s
提交时间	2022-10-27 14:49:24	内存使用	52.66 MiB

#include "bits/stdc++.h"

const int N = 1e5 + 10, M = 1e6 + 10;
int n, m;
int a[N], min[N], max[N];
std::vector<int> to[M], from[M];
std::map<int, bool> st;

void spfa() {
    std::queue<int> q;
    q.push(1), st[1] = true;
    while (q.size()) {
        int u = q.front(); q.pop();
        st[u] = false;
        for (auto v : to[u]) {
            if (std::min(min[u], a[v]) < min[v]) {
                min[v] = std::min(min[u], a[v]);
                if (!st[v]) {
                    q.push(v),
                    st[v] = true;
                }
            } 
        }
    }
    while (q.size()) q.pop();
    st.clear();
    q.push(n), st[n] = true;
    while (q.size()) {
        int u = q.front(); q.pop();
        st[u] = false;
        for (auto v : from[u]) {
            if (std::max(max[u], a[v]) > max[v]) {
                max[v] = std::max(max[u], a[v]);
                if (!st[v]) {
                    q.push(v);
                    st[v] = true;
                }
            }
        }
    }
}

int main() {
    freopen("trade.in", "r", stdin); 
    freopen("trade.out", "w", stdout);
    memset(min, 0x3f, sizeof min);
    std::cin >> n >> m;
    for (int i = 1; i <= n; ++ i) {
        std::cin >> a[i];
    }
    for (int i = 1; i <= m; ++ i) {
        int x, y, z;
        std::cin >> x >> y >> z;
        to[x].emplace_back(y), 
        from[y].emplace_back(x);
        if (z == 2) {
            to[y].emplace_back(x),
            from[x].emplace_back(y);
        }
    }
    spfa();
    int ans = 0;
    for (int i = 1; i <= n; ++ i) {
        ans = std::max(ans, max[i] - min[i]);
    }
    std::cout << ans << '\n';
    return 0;
}