思路：d(i, 0)表示从节点i到达大运村的最短路径，d(i, 1)表示从节点i到达大运村的次短路径。
1.最短路：当做DAG处理即可。
2.次短路：假设当前在u点处，下一个节点是v。v到终点的最短路是d(v, 0)，次短路是d(v, 1)，u到v的距离是w(u, v)，只能*一条路，即只能删除一条边。分成两种情况：
a.将*用在了v点到达终点的路上，则此时GG拥有主动权，可以选择最小的路径，即Imin = min(w(u, v) + d(v, 1))，;
b.将*用在u-v这条路径上面，则此时城管拥有主动权，可以*最短路径，则GG这能选择次短路径Hmin。
则d(u, 1) = max(Imin, Hmin)
AC代码
#include <cstdio>
#include <cmath>
#include <algorithm>
#include <cstring>
#include <utility>
#include <string>
#include <iostream>
#include <map>
#include <set>
#include <vector>
#include <queue>
#include <stack>
using namespace std;
#pragma comment(linker, "/STACK:1024000000,1024000000")
#define eps 1e-10
#define inf 0x3f3f3f3f
#define PI pair<int, int>
typedef long long LL;
const int maxn = 10000 + 5;
int n, m;
int d[maxn][2], in[maxn], Top[maxn], c[maxn*20];
struct Edge{
int from, to, dist, nex;
Edge() {}
Edge(int u, int v, int d, int ne):from(u), to(v), dist(d), nex(ne){}
}edge[maxn*20];
int edgenum, head[maxn];
void add_edge(int u, int v, int dis) {
edge[edgenum] = Edge(u, v, dis, head[u]);
head[u] = edgenum++;
}
void topsort() { //逆向拓扑序
queue<int>q;
for(int i = 0; i < n; ++i) if(!in[i]) q.push(i);
int num = 0;
while(!q.empty()) {
int u = q.front(); q.pop();
for(int i = head[u]; i != -1; i = edge[i].nex) if(i&1){
int v = edge[i].to;
--in[v];
if(!in[v]) q.push(v);
}
Top[num++] = u;
}
}
void solve(int u) {
if(u == n-1) {d[u][0] = d[u][1] = 0; return;} //终点
int num = 0, Imin = inf;
for(int i = head[u]; i != -1; i = edge[i].nex) if(!(i&1)){
int v = edge[i].to;
//最短路
d[u][0] = min(d[u][0], d[v][0] + edge[i].dist);
//次短路
Imin = min(Imin, d[v][1] + edge[i].dist); // GG掌握主动权
c[num++] = d[v][0] + edge[i].dist; //城管有主动权
}
if(num < 2) {d[u][1] = inf; return;} //GG无法到达从u到达终点
int fir = c[0], sec = c[1]; //最小和次小
if(fir > sec) swap(fir, sec);
for(int i = 2; i < num; ++i) {
if(c[i] <= fir) {
sec = fir;
fir = c[i];
}
else sec = min(sec, c[i]);
}
d[u][1] = max(Imin, sec);
if(d[u][1] > inf) d[u][1] = inf;
if(d[u][0] > inf) d[u][0] = inf;
}
int main() {
int T;
scanf("%d", &T);
while(T--) {
edgenum = 0;
memset(head, -1, sizeof(head));
memset(d, inf, sizeof(d));
memset(in, 0, sizeof(in));
scanf("%d%d", &n, &m);
int u, v, dis;
for(int i = 0; i < m; ++i) {
scanf("%d%d%d", &u, &v, &dis);
add_edge(u, v, dis);
add_edge(v, u, dis);
in[u]++;
}
topsort();
for(int i = 0; i < n; ++i) {
solve(Top[i]);
}
if(d[0][1] >= inf) printf("-1\n");
else printf("%d\n", d[0][1]);
}
return 0;
}
如有不当之处欢迎指出！