题目链接
次短路模板题。
对每个点记录最短路和严格次短路，然后就是维护次值的方法了。
和这题一样。
#include <cstdio>
#include <queue>
#include <cstring>
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 <int> 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
", dis[n][1]);
return 0;
}