题目大意
给定$n$个点和$m$条边，这$m$条边其中有一条是不能走的，但不知道是哪一条，要求求出从$1$到$n$的最短路花费的最大时间。
解题思路
先求出一个最短路，将其路径记录下来。然后枚举删掉最短路中的每一条边，再跑最短路，答案取其最大值
那么怎么记录路径呢？引入一个前驱数组$pre$，表示节点i的前驱是$pre_i$。
附上代码
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <queue>
#include <vector>
#include <cstring>
using namespace std;
typedef pair<
int,
int>
P;
priority_queue<P, vector<P>, greater<P> >
Q;
const int maxedge = (1e3*1e3+
3) *
2;
const int maxnode = 1e3+
3;
int n, m, fir[maxnode], nx[maxedge], dis[maxnode], cnt, Ans;
int u[maxedge], v[maxedge], w[maxedge], pre[maxnode];
bool use[maxedge], cut[maxnode][maxnode], mark;
inline void addedge(
int x,
int y,
int z) {
nx[++cnt] =
fir[x];
fir[x] =
cnt;
u[cnt] = x, v[cnt] = y, w[cnt] =
z;
}
inline void Dijkstra() {
fill(dis+
1, dis+
1+n,
1234567890);
Q.push(P(0,
1));
dis[1] =
0;
int k;
P x;
while (!
Q.empty()) {
x =
Q.top();
Q.pop();
if(x.first >
dis[x.second])
continue;
k =
fir[x.second];
while (k != -
1) {
if(x.first + w[k] < dis[v[k]] && !
cut[u[k]][v[k]]) {
if(!mark) pre[v[k]] =
u[k];
dis[v[k]] = x.first +
w[k];
Q.push(P(dis[v[k]], v[k]));
}
k =
nx[k];
}
}
}
int main() {
scanf("%d%d", &n, &
m);
memset(fir, -
1,
sizeof(fir));
int x, y, z;
for(
int i=
1; i<=m; i++
) {
scanf("%d%d%d", &x, &y, &
z);
addedge(x, y, z);
addedge(y, x, z);
}
Dijkstra();
mark =
1;
for(
int i=n; i!=
1; i =
pre[i]) {
cut[pre[i]][i] =
1;
cut[i][pre[i]] =
1;
Dijkstra();
cut[pre[i]][i] =
0;
cut[i][pre[i]] =
0;
Ans =
max(Ans, dis[n]);
}
printf("%d", Ans);
}
转载于:https://www.cnblogs.com/bljfy/p/9447320.html
相关资源：锣鼓声声迎新春——新年工作计划ppt模板.zip
