#include using namespace std; typedef pair 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, greater> 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 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; }