DP -> 最短路 -> SPFA 224ms
#include <bits/stdc++.h>
using namespace std;
const int N = 100010, M = 2000010;
int n, m;
int price[N];
int h[N], rh[N], e[M], ne[M], idx;
int dmin[N], dmax[N];
bool st[N];
void add(int h[], int a, int b) {
e[idx] = b, ne[idx] = h[a], h[a] = idx++;
}
void spfa(int ts, int h[], bool flag, int dist[]) {
queue<int> que;
dist[ts] = price[ts];
que.push(ts);
st[ts] = true;
while (que.size()) {
int t = que.front(); que.pop();
st[t] = false;
for (int i = h[t]; ~i; i = ne[i]) {
int j = e[i];
if (flag && dist[j] > min(dist[t], price[j])|| !flag && dist[j] < max(dist[t], price[j])) {
if (flag) dist[j] = min(dist[t], price[j]);
else dist[j] = max(dist[t], price[j]);
if (st[j]) continue;
que.push(j);
st[j] = true;
}
}
}
}
int main() {
memset(h, -1, sizeof(h));
memset(rh, -1, sizeof(h));
scanf("%d%d", &n, &m);
for (int i = 1; i <= n; i++) scanf("%d", &price[i]);
int x, y, z;
while (m--) {
scanf("%d%d%d", &x, &y, &z);
add(h, x, y), add(rh, y, x);
if (z == 2) add(h, y, x), add(rh, x, y);
}
memset(dmin, 0x3f, sizeof(dmin));
spfa(1, h, true, dmin);
spfa(n, rh, false, dmax);
int res = 0;
for (int i = 1; i <= n; i++) res = max(res, dmax[i] - dmin[i]);
printf("%d", res);
return 0;
}
记忆化搜索 176ms
#include <bits/stdc++.h>
using namespace std;
const int N = 1e5 + 10, M = 2e6 + 10;
int n, m;
int price[N];
int h[N], rh[N], e[M], ne[M], idx;
int dmin[N], dmax[N];
void add(int h[], int a, int b) {
e[idx] = b, ne[idx] = h[a], h[a] = idx++;
}
void dfs_min(int u, int val) {
if (val >= dmin[u]) return;
dmin[u] = min(price[u], val);
val = min(val, dmin[u]);
for (int i = h[u]; ~i; i = ne[i]) {
int j = e[i];
dfs_min(j, val);
}
}
void dfs_max(int u, int val) {
if (val <= dmax[u]) return;
dmax[u] = max(price[u], val);
val = max(val, dmax[u]);
for (int i = rh[u]; ~i; i = ne[i]) {
int j = e[i];
dfs_max(j, val);
}
}
int main() {
memset(h, -1, sizeof(h));
memset(rh, -1, sizeof(rh));
scanf("%d%d", &n, &m);
for (int i = 1; i <= n; i++) scanf("%d", &price[i]);
int x, y, z;
while (m--) {
scanf("%d%d%d", &x, &y, &z);
add(h, x, y), add(rh, y, x);
if (z == 2) add(h, y, x), add(rh, x, y);
}
memset(dmin, 0x3f, sizeof(dmin));
dfs_min(1, price[1]);
dfs_max(n, price[n]);
int res = 0;
for (int i = 1; i <= n; i++) res = max(res, dmax[i] - dmin[i]);
printf("%d", res);
return 0;
}