次短路模板题。
对每个点记录最短路和严格次短路，然后就是维护次值的方法了。
和一样。
#include #include #include using namespace std;inline int read(){ int s = 0, w = 1; char ch = getchar(); while(ch < '0' || ch > '9'){ if(ch == '-') w = -1; ch = getchar(); } while(ch >= '0' && ch <= '9'){ s = s * 10 + ch - '0'; ch = getchar(); } return s * w;}const int MAXN = 5010;const int MAXM = 200010;struct Edge{ int next, to, dis;}e[MAXM];int head[MAXN], num, dis[MAXN][2], vis[MAXN];inline void Add(int u, int v, int w){ e[++num].to = v; e[num].next = head[u]; e[num].dis = w; head[u] = num; e[++num].to = u; e[num].next = head[v]; e[num].dis = w; head[v] = num;}int a, b, c, now, n, m;queue q;int main(){ n = read(); m = read(); while(m--){ a = read(); b = read(); c = read(); Add(a, b, c); } for(int i = 1; i <= n; ++i) dis[i][0] = dis[i][1] = 2147483647 >> 1; dis[1][0] = 0; q.push(1); while(q.size()){ now = q.front(); q.pop(); vis[now] = 0; for(int i = head[now]; i; i = e[i].next){ int v = e[i].to; #define u now if(dis[v][0] > dis[u][0] + e[i].dis){ dis[v][1] = dis[v][0]; dis[v][0] = dis[u][0] + e[i].dis; if(!vis[v]) q.push(v), vis[v] = 1; } else if(dis[v][1] > dis[u][0] + e[i].dis && dis[u][0] + e[i].dis != dis[v][0]){ dis[v][1] = dis[u][0] + e[i].dis; if(!vis[v]) q.push(v), vis[v] = 1; } if(dis[v][1] > dis[u][1] + e[i].dis && dis[u][1] + e[i].dis != dis[v][0]){ dis[v][1] = dis[u][1] + e[i].dis; if(!vis[v]) q.push(v), vis[v] = 1; } } } printf("%d\n", dis[n][1]); return 0;}