【洛谷P1186】玛丽卡DescriptionSolutionCode

Description

麦克找了个新女朋友，玛丽卡对他非常恼火并伺机报复。

因为她和他们不住在同一个城市，因此她开始准备她的长途旅行。

在这个国家中每两个城市之间最多只有一条路相通，并且我们知道从一个城市到另一个城市路上所需花费的时间。

麦克在车中无意中听到有一条路正在维修，并且那儿正堵车，但没听清楚到底是哪一条路。无论哪一条路正在维修，从玛丽卡所在的城市都能到达麦克所在的城市。

玛丽卡将只从不堵车的路上通过，并且她将按最短路线行车。麦克希望知道在最糟糕的情况下玛丽卡到达他所在的城市需要多长时间，这样他就能保证他的女朋友离开该城市足够远。

编写程序，帮助麦克找出玛丽卡按最短路线通过不堵车道路到达他所在城市所需的最长时间(用分钟表示)。

Solution

找出在一条边断掉的情况下的单源最短路径，并输出最坏的情况（去边不同会影响最短路）。

完了？？？

完了。。。

所以思路就出来了：一一去掉所有边，分别去求最短路。

仔细想想：时间复杂度（Dijkstra）O(n^2*m)

如果是dalao写带堆优化的也会到 O(nlogn*m)

但是！

时间复杂度实在是太高了！！！

怎么办？？？

不慌，慌也没用。

我们不是分析过题吗？去掉一条边的单源最短路。如果去的边不是不删边情况下的单源最短路径上的边，那么会对最终答案有影响吗？

没有！

所以，我们只需要看一看单源最短路上的边分别去掉会是什么情况就可以了。正常操作是先跑一遍Dijkstra（最短路），然后再去记录单源最短路上经过的边，把路过的边分别去掉，分别跑一边单源最短路取最大值就好啦！

Code

 

#include <bits/stdc++.h>
#define pa pair<int, int>
#define mp make_pair
using namespace std;
priority_queue<pa, vector<pa>, greater<pa> >q;
int n, m, num = 1;
int pre[1010], bian[1010], b[100010];
int head[1000010], dis[1010], vis[1010];
inline int read() {
int ret = 0, op = 1;
char c = getchar();
while (!isdigit(c)) {
if (c == '-') op = -1;
c = getchar();
}
while (isdigit(c)) {
ret = (ret << 3) + (ret << 1) + c - '0';
c = getchar();
}
return ret * op;
}
struct emmm {
int nxt, to ,dis;
}e[1000010];
void add(int from, int to, int dis) {
e[++num].nxt = head[from];
e[num].dis = dis;
e[num].to = to;
head[from] = num;
}
void dijkstra() {
memset(dis, 0x3f, sizeof(dis));
memset(vis, 0, sizeof(vis));
q.push(mp(0, 1));
dis[1] = 0;
while (!q.empty()) {
int now = q.top().second;
q.pop();
if (vis[now]) continue;
vis[now] = 1;
for (int i = head[now];i; i = e[i].nxt) {
int v = e[i].to;
if (dis[v] > dis[now] + e[i].dis) {
dis[v] = dis[now] + e[i].dis;
pre[v] = now;
bian[v] = i;
q.push(mp(dis[v], v));
}
}
}
}
int main() {
n = read();m = read();
int x, y, z;
for (int i = 1;i <= m; i++) {
x = read();
y = read();
z = read();
add(x, y, z);
add(y, x, z);
}
dijkstra();
int ans = dis[n], now = n, sum = 0;
while (now != 1) {
b[++sum] = bian[now];
now = pre[now];
}
for (int i = 1;i <= sum; i++) {
int k = e[b[i]].dis;
e[b[i]].dis = 9999999;
e[b[i]^1].dis = 9999999;
dijkstra();
ans = max(ans, dis[n]);
e[b[i]].dis = k;
e[b[i]^1].dis = k;
}
cout << ans << endl;
return 0;
}