2625: 【USACO2014FebGold】Roadblock
Description
【题目描述】
有一个无向图，共N个节点，编号1至N，共M条边。FJ在节点1，它想到达节点N。FJ总是会选择最短路径到达节点N。作为捣蛋的奶牛Bessie，它想尽量延迟FJ到达节点N的时间，于是Bessie决定从M条边之中选择某一条边，使得该边的长度变成原来的两倍，由于智商的问题，Bessie不知道选择加倍哪条边的长度才能使得FJ到达N号节点的时间最迟。注意：不管Bessie选择加倍哪条边的长度，FJ总是会从1号节点开始走最短路径到达N号点。
【输入样例】
第一行，两个整数N和M. 1 <=N<=250, 1<=M<=250000。
接下来有M行，每行三个整数：A，B，L，表示节点A和节点B之间有一条长度为L的无向边。1<=L<=1000000。
【输出样例】
一个整数。Bessie选择了加倍某一条边的长度后，奶牛FJ从节点1到达节点N的最短路径是多少。但是输出的格式有变化，假设Bessie没有加倍某一条边的长度之前，FJ从1号节点到达N号节点的最短路径是X；在Bessie加倍某一条边的长度之后，FJ从1号节点到达N号节点的最短路径是Y，那么你输出的结果是Y-X。
【输入样例】
5 7
2 1 5
1 3 1
3 2 8
3 5 7
3 4 3
2 4 7
4 5 2
【输出样例】
2（把节点3到节点4的边从原来的长度3变成长度6）
HINT
Solution Notes (Neal Wu): This problem is a standard occurrence of the shortest path problem, except that we can now choose a single edge to be doubled and would like to choose the edge that maximizes the new shortest path.
Notice that once we have chosen an edge, we can compete the shortest path easily in either O(M log N) or O(N^2) time, by simply modifying the edge length and performing Dijkstra's shortest path algorithm. However since there are M edges this gives an O(M^2) overall complexity, which was intended to be too slow.
To improve the complexity, we can notice that if the edge we choose to double is not on the original shortest path from 1 to N, then the final shortest path length stays the same. This means we only need to try doubling the edges on the original shortest path from 1 to N, and there are only O(N) of them. This gives us a better complexity of either O(NM log N) or O(N^3), the latter of which is implemented below.
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <vector>
using namespace std;
FILE *in = fopen ("rblock.in", "r"), *out = fopen ("rblock.out", "w");
const int MAXN = 505;
int N, M, edge [MAXN][MAXN], dist [MAXN], prev [MAXN];
bool visited [MAXN];
int best_path (int start, int end)
{
memset (dist, 63, sizeof (dist));
memset (visited, false, sizeof (visited));
memset (prev, -1, sizeof (prev));
dist [start] = 0;
while (true)
{
int close = -1;
for (int i = 0; i < N; i++)
if (!visited [i] && (close == -1 || dist [i] < dist [close]))
close = i;
if (close == -1)
break;
visited [close] = true;
for (int i = 0; i < N; i++)
{
int ndist = dist [close] + edge [close][i];
if (ndist < dist [i])
{
dist [i] = ndist;
prev [i] = close;
}
}
}
return dist [end];
}
int main ()
{
memset (edge, 63, sizeof (edge));
fscanf (in, "%d %d", &N, &M);
for (int i = 0; i < M; i++)
{
int a, b, len;
fscanf (in, "%d %d %d", &a, &b, &len);
a--; b--;
edge [a] = edge [a] = len;
}
int original = best_path (0, N - 1);
vector <int> path;
for (int i = N - 1; i != -1; i = prev [i])
path.push_back (i);
int most_doubled = original;
for (int i = 0; i + 1 < (int) path.size (); i++)
{
int a = path [i], b = path [i + 1];
edge [a] *= 2;
edge [a] *= 2;
most_doubled = max (most_doubled, best_path (0, N - 1));
edge [a] /= 2;
edge [a] /= 2;
}
fprintf (out, "%d\n", most_doubled - original);
return 0;
}