Roadblocks
| Time Limit: 2000MS | Memory Limit: 65536K | |
|---|---|---|
| Total Submissions: 19715 | Accepted: 6914 |
Description
Bessie has moved to a small farm and sometimes enjoys returning to visit one of her best friends. She does not want to get to her old home too quickly, because she likes the scenery along the way. She has decided to take the second-shortest rather than the shortest path. She knows there must be some second-shortest path.
The countryside consists of R (1 ≤ R ≤ 100,000) bidirectional roads, each linking two of the N (1 ≤ N ≤ 5000) intersections, conveniently numbered 1..N. Bessie starts at intersection 1, and her friend (the destination) is at intersection N.
The second-shortest path may share roads with any of the shortest paths, and it may backtrack i.e., use the same road or intersection more than once. The second-shortest path is the shortest path whose length is longer than the shortest path(s) (i.e., if two or more shortest paths exist, the second-shortest path is the one whose length is longer than those but no longer than any other path).
Input
Line 1: Two space-separated integers: N and R
Lines 2..R+1: Each line contains three space-separated integers: A, B, and D that describe a road that connects intersections A and B and has length D (1 ≤ D ≤ 5000)
Output
Line 1: The length of the second shortest path between node 1 and node N
Sample Input
4 4
1 2 100
2 4 200
2 3 250
3 4 100Sample Output
450Hint
Two routes: 1 -> 2 -> 4 (length 100+200=300) and 1 -> 2 -> 3 -> 4 (length 100+250+100=450)
Source
链接
http://poj.org/problem?id=3255
题意
求1到N的次短路。
题解
两种办法。
在求最短路的时候记录次短路，先更新最短路，然后更新次短路具体可参考：传送门。
如果dist[v]表示s->v的最短距离，dist2[v]表示s->v的次短距离，d为s->v的第k短距离(k>1)。那么一定满足这样一个关系，dist[v] < dist2[v] <= k[雾]。看到这个等式的时候我们可以发现，如果dist2[v] > d2 > dist[v]，显然这时候我们需要将dist2[v]更新为d2。那么我们只要找到不满足dist[v] < dist2[v] <= k[雾]这个的式子的dist2[v]，那么我们就更新他。一直更新到所以式子都满足这个式子，那么dist2[v]就为源点s->v的次短路。到此我们已经推出了求解次短路的方法。
两次最短路（起点$\rightarrow$终点，终点$\rightarrow$起点），然后再枚举每一条边，如果dist1[A] + $W_{AB}$ + dist2[B] > dist1[n]，那么保存值并更新，得到次短路，具体可参考：传送门。
求次短路，可以通过求最短路得到次短路长度
1到n的次短路长度必然产生于：从1走到x的最短路 +edge[x][y]+ y到n的最短路
首先预处理好1到每一个节点的最短路，和n到每一个节点的最短路
然后枚举每一条边作为中间边（x，y）或者（y，x），如果加起来长度等于最短路长度则跳过，否则更新。
从1走到x的最短路 + edgex + y到n的最短路 给dist[n] 比较 找大于dist[n] 且是最小的那一个
代码
- Accepted 3612K 219MS 1749B
#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <queue>
#include <vector>
using namespace std;
const int maxn = 5010;
const int maxm = 100010;
const int inf = 0x3f3f3f3f;
int dist[maxn], dist2[maxn];
int n, m;
struct Node
{
int v, dis;
Node(int _v, int _dis): v(_v), dis(_dis) {}
bool operator < (const Node & r) const
{
return dis > r.dis;
}
};
struct Edge
{
int to, cost;
Edge(int _to, int _cost): to(_to), cost(_cost) {}
};
vector <Edge> edge[maxn];
void addedge(int u, int v, int w)
{
edge[u].push_back(Edge(v, w));
}
void dijkstra(int s)
{
for (int i = 0; i <= n; ++i)
dist[i] = dist2[i] = inf;
dist[s] = 0, dist2[s] = inf;
priority_queue <Node> Q;
Q.push(Node(s, dist[s]));
while (!Q.empty())
{
Node tmp = Q.top();
Q.pop();
int u = tmp.v, dis = tmp.dis;
if (dis > dist2[u]) // 距离大于次短路
continue;
for (int i = 0; i < edge[u].size(); ++i)
{
int v = edge[u][i].to, cost = edge[u][i].cost;
int w = cost + dis; // 边权加上当前的一个最短/次短距离
if (dist[v] > w) // 更新最短路
{
swap(dist[v], w); // 更新dist[v]/w
Q.push(Node(v, dist[v]));
}
if (dist2[v] > w && dist[v] < w) // 更新次短路
{
dist2[v] = w;
Q.push(Node(v, dist2[v]));
}
}
}
}
int main()
{
int u, v, w;
while (scanf("%d%d", &n, &m) != EOF)
{
for (int i = 0; i < m; ++i)
{
scanf("%d%d%d", &u, &v, &w);
addedge(u, v, w);
addedge(v, u, w);
}
dijkstra(1);
printf("%d\n", dist2[n]);
}
return 0;
}或者使用两次dijkstra，然后一遍循环。
int ans = inf, tmp;
for (int i = 1; i <= n; ++i)
{
for (int j = 0; j < edge[i].size(); ++j)
{
int v = edge[i][j].to, w = edge[i][j].cost;
tmp = dist1[i] + dist2[v] + w;
if (tmp > dist1[n] && tmp < ans)
ans = tmp;
}
}The end.
2018-08-30 星期四