POJ 3255 Roadblocks and 3463 Sightseeing（次短路）
POJ 3255 Roadblocks
N个点，M条双向边，求1到N的严格次短路
Idea 1
1到n的次短路长度必然产生于：从1走到x的最短路 + edge[x][y] + y到n的最短路
首先预处理好1到每一个节点的最短路，和n到每一个节点的最短路
然后枚举每一条边作为中间边（x，y）或者（y，x），如果加起来长度等于最短路长度则跳过，否则更新从1走到x的最短路 + edge[x][y] + y到n的最短路 给dist[n] 比较 找大于dist[n] 且是最小的那一个
spfa(1) + spfa(n)
原文链接： https://blog.csdn.net/huangshuai147/article/details/69105576
Code
#include <queue>
#include <cstdio>
#include <string>
#include <cstring>
#include <iostream>
#include <algorithm>
using namespace std;
const int INF = 0x3f3f3f3f;
int n, m;
int cnt;
struct edge
{
int to, w, pre;
} a[200005];
bool vis[5005];///表示是否在队列里
int head[5005], frdis[5005], redis[5005], tot, sum;
void add(int from, int to, int w)
{
a[cnt].to = to;
a[cnt].w = w;
a[cnt].pre = head[from];
head[from] = cnt;
cnt++;
}
void init()
{
cnt = 0;
for(int i = 0; i <= n; ++i)
{
frdis[i] = INF;
redis[i] = INF;
head[i] = -1;
vis[i] = 0;
}
}
void spfa(int start, int * dis)
{
memset(vis, 0, sizeof(vis));
deque<int> q;
dis[start] = 0;
q.push_front(start);
vis[start] = 1;///表示在队列里
tot = 1, sum = 0;
while(q.size())
{
int first = q.front();
q.pop_front();
vis[first] = 0;
tot--;
sum -= dis[first];
///同dijkstra，以first为中转点，而非a[i].from
for(int i = head[first]; ~i; i = a[i].pre)
{
int t = a[i].to;
if(dis[t] > dis[first] + a[i].w)
{
dis[t] = dis[first] + a[i].w;
if(!vis[t])
{
vis[t] = 1;
if(q.empty() || dis[t] > dis[q.front()] || dis[t] * tot >= sum)
q.push_back(t);
else
q.push_front(t);
sum += dis[t];
tot++;
}
}
}
}
return ;
}
int main()
{
scanf("%d%d", &n, &m);
init();
int u, v, w;
for(int i = 0; i < m; ++i)
{
scanf("%d%d%d", &u, &v, &w);
add(u, v, w);
add(v, u, w);
}
spfa(1, frdis);
spfa(n, redis);
int ans = INF;
for(int i = 1; i <= n; ++i)
for(int j = head[i]; ~j; j = a[j].pre)
{
v = a[j].to;
w = a[j].w;
int tem = frdis[i] + w + redis[v];
if(tem > frdis[n] && tem < ans)
ans = tem;
}
cout << ans << '\n';
return 0;
}
POJ 3463 Sightseeing
N个点，M条单向边，求最短路数目+比最短路长单位1的次短路条数
Idea 2
（s，u，v）代表从s——v的最短路，u是中间一个必经点
最短路和次短路的比较:
(s，u，v）最短路=到达前一个点u的最短路+（u，v）的最短路。
因而最短路求解有两种情况：
- （s，u，v）次短路=到达前一个点u的次短路+（u，v）的最短路
- （s，u，v）次短路=到达前一个点u的最短路+（u，v）的次短路。
用：d[v][0]代表最短路，d[v][1]代表次短路。
（一）如果从s—u的最短路加上（u，v）权值的距离小于原来的d[v][0] ，我们就可把次短路d[v][1] 的值更新为d[v][0]，就该题而言，此时可以把次短路的条数也更新为这个点的最短路的条数；把当前最短路d[v][0]的值更新成最小的，和原来最短路的松弛操作是一样的。
（二）如果从s—u的最短路加上（u，v）权值的距离大于原来的d[v][0]，这就说明这条路路径就可能是一条次短路，那我们需要判断这条路的值dist，和原来的次短路的值d[v][1]进行比较！
- 如果它比原来的次短路要大，直接跳过.
- 如果它比原来的次短路要小，那么我们就需要更新最短路的长度 .
- 如果与原来的次短路相等，说明我们的次短路有另一种（这里并不一定是只有1种）方法可以到达终点v。这里要加的种类是：原来到v点的次短路的条数+到u点的次短路（或者最短路，（u，v）并不知道是不是一定是最短路，如果是次短路，那么此时加的就是到u的最短路）的条数。
Code
#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
using namespace std;
const int INF = 0x3f3f3f3f;
const int N = 10005;
struct edge
{
int to, w, pre;
}a[N << 1];
int n, m, cnt, head[N], d[N][2], c[N][2], vis[N][2];
void add(int from, int to, int w)
{
a[cnt].to = to;
a[cnt].w = w;
a[cnt].pre = head[from];
head[from] = cnt++;
}
void Dijkstra(int s)
{
memset(d, INF, sizeof(d));
memset(c, 0, sizeof(c));
memset(vis, 0, sizeof(vis));
d[s][0] = 0;
c[s][0] = 1;
int pos = s, idx;
while(1)
{
pos = -1;
for(int i = 1; i <= n; ++i)
for(int j = 0; j < 2; ++j)
if(!vis[i][j] && (pos == -1 || d[i][j] < d[pos][idx]))
pos = i, idx = j;
if(pos == -1)
break;
vis[pos][idx] = 1;
for(int i = head[pos]; ~i; i = a[i].pre)
{
int to = a[i].to;
int dis = d[pos][idx] + a[i].w;
if(dis < d[to][0])///This path is shorter than the shortest path.
{
d[to][1] = d[to][0], c[to][1] = c[to][0];
d[to][0] = dis, c[to][0] = c[pos][idx];
}
else if(dis == d[to][0])
c[to][0] += c[pos][idx];
else if(dis < d[to][1])///longer than the shortest but shorter than the second shortest
d[to][1] = dis, c[to][1] = c[pos][idx];
else if(dis == d[to][1])
c[to][1] += c[pos][idx];
}
}
}
int main()
{
int t;
cin >> t;
while(t--)
{
cnt = 0;
memset(head, -1, sizeof(head));
scanf("%d%d", &n, &m);
int u, v, w;
for(int i = 0; i < m; ++i)
{
scanf("%d%d%d", &u, &v, &w);
add(u, v, w);
}
int start, over;
scanf("%d%d", &start, &over);
Dijkstra(start);
int ans = c[over][0];
if(d[over][1] == d[over][0] + 1)///be careful which is smaller
ans += c[over][1];
cout << ans << '\n';
}
return 0;
}
POJ 3255 of Idea 2
#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
using namespace std;
const int INF = 0x3f3f3f3f;
const int M = 100005;
const int N = 5005;
struct edge
{
int to, w, pre;
} a[M << 1];
int n, m, cnt, head[N], d[N][2], vis[N][2];
void add(int from, int to, int w)
{
a[cnt].to = to;
a[cnt].w = w;
a[cnt].pre = head[from];
head[from] = cnt++;
}
void Dijkstra(int s)
{
memset(d, INF, sizeof(d));
memset(vis, 0, sizeof(vis));
d[s][0] = 0;
int pos = s, idx;
while(1)
{
pos = -1;
for(int i = 1; i <= n; ++i)
for(int j = 0; j < 2; ++j)
if(!vis[i][j] && (pos == -1 || d[i][j] < d[pos][idx]))
pos = i, idx = j;
if(pos == -1)
break;
vis[pos][idx] = 1;
for(int i = head[pos]; ~i; i = a[i].pre)
{
int to = a[i].to;
int dis = d[pos][idx] + a[i].w;
if(dis < d[to][0])///This path is shorter than the shortest path.
d[to][1] = d[to][0], d[to][0] = dis;
else if(dis < d[to][1])///longer than the shortest but shorter than the second shortest
d[to][1] = dis;
}
}
}
int main()
{
cnt = 0;
memset(head, -1, sizeof(head));
scanf("%d%d", &n, &m);
int u, v, w;
for(int i = 0; i < m; ++i)
{
scanf("%d%d%d", &u, &v, &w);
add(u, v, w);
add(v, u, w);
}
Dijkstra(1);
cout << d[n][1] << '\n';
return 0;
}