记录编号	42383	评测结果	AAAAAAAAAA
题目名称	[NOIP 2009]最优贸易	最终得分	100
用户昵称	王者自由	是否通过	通过
代码语言	C++	运行时间	0.276 s
提交时间	2012-09-21 12:04:18	内存使用	3.74 MiB

#include <cstdio>
#include <queue>
#include <vector>
#include <algorithm>
using namespace std;
const int N = 100000 + 10, INF = 0x7fffffff;
int n, m, c[N], a[2][N], s;
vector<int> G[2][N];
inline bool cmp(int k, int x, int y) {
    return k ? x > y : x < y;
}
void SPFA(int s, int k) {
    queue<int> q;
    a[k][s] = c[s], q.push(s);
    while(!q.empty()) {
        int u = q.front(); q.pop();
        for(int j=0; j<G[k][u].size(); j++) {
            int v = G[k][u][j];
            if(cmp(k, a[k][u], a[k][v])) {
                a[k][v] = a[k][u], q.push(v);
                if(cmp(k, c[v], a[k][v]))
                    a[k][v] = c[v];
            }
        }
    }
}
int main() {
    freopen("trade.in", "r", stdin);
    freopen("trade.out", "w", stdout);
    scanf("%d %d", &n, &m);
    for(int i=1; i<=n; i++)
        scanf("%d", c+i);
    int x, y, z;
    for(int i=1; i<=m; i++) {
        scanf("%d %d %d", &x, &y, &z);
        G[0][x].push_back(y), G[1][y].push_back(x);
        if(z > 1) G[0][y].push_back(x), G[1][x].push_back(y);
    }
    for(int i=1; i<=n; i++)
        a[0][i] = INF, a[1][i] = 0;
    SPFA(1, 0);
    SPFA(n, 1);
    for(int i=1; i<=n; i++)
        s = max(s, a[1][i] - a[0][i]);
    printf("%d\n", s);
    return 0;
}