贝茜把家搬到了一个小农场，但她常常回到FJ的农场去拜访她的朋友。贝茜很喜欢路边的风景，不想那么快地结束她的旅途，于是她每次回农场，都会选择第二短的路径，而不象我们所习惯的那样，选择最短路。 贝茜所在的乡村有R(1<=R<=100,000)条双向道路，每条路都联结了所有的N(1<=N<=5000)个农场中的某两个。贝茜居住在农场1，她的朋友们居住在农场N（即贝茜每次旅行的目的地）。 贝茜选择的第二短的路径中，可以包含任何一条在最短路中出现的道路，并且，一条路可以重复走多次。当然咯，第二短路的长度必须严格大于最短路（可能有多条）的长度，但它的长度必须不大于所有除最短路外的路径的长度。
如题，就是次短路而已，用SPFA或者Dij都行。
不过这次我使用了Dij，由于要求次短路，那么外层的循环要有2*n-1次了，可以说成里边有n-1次求最短路的，n次求次短路的
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cstring>
#include <cmath>
#define MAXM 222222
#define MAXN 5555
#define INF 1000000007
using namespace std;
struct node
{int v, next, w;
}edge[MAXM];
int d[MAXN][2], e, n, m;
int cnt[MAXN][2];
int head[MAXN];
bool vis[MAXN][2];
void init()
{e = 0;memset(head, -1, sizeof(head));
}
void insert(int x, int y, int w)
{edge[e].v = y;edge[e].w = w;edge[e].next = head[x];head[x] = e++;
}
int dijkstra(int s, int t)
{int flag, u;memset(vis, 0, sizeof(vis));for(int i = 1; i <= n; i++)d[i][0] = d[i][1] = INF;d[s][0] = 0;for(int i = 1; i < 2 * n; i++){int mini = INF;for(int j = 1; j <= n; j++){if(!vis[j][0] && d[j][0] < mini){u = j;flag = 0;mini = d[j][0];}else if(!vis[j][1] && d[j][1] < mini){u = j;flag = 1;mini = d[j][1];}}if(mini == INF) break;vis[u][flag] = 1;for(int j = head[u] ; j != -1; j = edge[j].next){int w = edge[j].w;int v = edge[j].v;if(d[v][0] > mini + w){d[v][1] = d[v][0];d[v][0] = mini + w;}else if(d[v][1] > mini + w)d[v][1] = mini + w;}}return d[t][1];
}
int main()
{int s, t, T, x, y, w;init();scanf("%d%d", &n, &m);for(int i = 1; i <= m; i++){scanf("%d%d%d", &x, &y, &w);insert(x, y, w);insert(y, x, w);}printf("%d\n", dijkstra(1, n));return 0;
}
然后还有个堆优化的
#include <iostream>
#include <cstdio>
#include <cstring>
#include <queue>
#define MAXN 5555
#define MAXM 222222
#define INF 1000000000
using namespace std;
struct Edge
{int to, cost;
};
typedef pair<int, int> P; //first是最短距离，second是点的标号
int n, r;
vector<Edge>g[MAXN];
int dis[MAXN];
int dis2[MAXN];
priority_queue<P, vector<P>, greater<P> >que;
void solve(int s, int t)
{for(int i = 1; i <= n; i++)dis[i] = dis2[i] = INF;dis[s] = 0;que.push(P(0, s));while(!que.empty()){P p = que.top();que.pop();int v = p.second, d = p.first;if(dis2[v] < d) continue;for(int i = 0; i < g[v].size(); i++){Edge e = g[v][i];int d2 = d + e.cost;if(dis[e.to] > d2){dis2[e.to] = dis[e.to];dis[e.to] = d2;que.push(P(dis[e.to], e.to));}else if(dis2[e.to] > d2){dis2[e.to] = d2;que.push(P(dis2[e.to], e.to));}}}printf("%d\n", dis2[t]);
}
int main()
{int s, t, T, x, y, w;scanf("%d%d", &n, &r);for(int i = 1; i <= r; i++){scanf("%d%d%d", &x, &y, &w);g[x].push_back({y, w});g[y].push_back({x, w});}solve(1, n);return 0;
}