这道题题目真的想吐槽一下...是在机房同学的解释下才看懂的。就是让你求在可以删一条边的情况下，并且删后保证可以到达终点时，求删了后的最大的最短路径。
70分暴力思路：
枚举删边，然后跑一下最短路即可，思路很简单，下面给出70分代码：
#include <bits/stdc++.h>
using namespace std;
vector<pair<int , int> > e[1010];
int n , m , ans;
int dis[1010] , vis[1010] , l[500010] , r[500010];
void work(int uu , int vv){
memset(dis , 127 , sizeof(dis));
memset(vis , 0 , sizeof(vis));
queue<int> q;
dis[1] = 0;
vis[1] = 1;
q.push(1);
while(!q.empty()){
int x = q.front();
q.pop();
vis[x] = 0;
for(int i = 0; i < e[x].size(); i++){
int y = e[x][i].first , w = e[x][i].second;
if((x == uu && y == vv) || (x == vv && y == uu)) continue; //不走这一条路
if(dis[y] > dis[x] + w){
dis[y] = dis[x] + w;
if(!vis[y]){
vis[y] = 1;
q.push(y);
}
}
}
}
ans = max(ans , dis[n]);
}
int main(){
cin >> n >> m;
for(int i = 1; i <= m; i++){
int x , y , z;
cin >> x >> y >> z;
l[i] = x , r[i] = y; //存储每一条边
e[x].push_back(make_pair(y , z));
e[y].push_back(make_pair(x , z));
}
for(int i = 1; i <= m; i++) work(l[i] , r[i]); //删除
cout << ans;
return 0;
}
100分满分思路：
我们先预处理求一遍最短路，当我们开始删边时，如果删的不是最短路径上的边时，那么答案还是原来的最短路，因为我们最短路要用的边一条没变。所以，我们只需要枚举删掉最短路上的边即可，这样答案一定改变，同时注意能达到终点。下面给出满分代码：
#include <bits/stdc++.h>
using namespace std;
vector<pair<int , int> > e[1010];
int n , m , ans;
int dis[1010] , vis[1010] , pre[1010];
void work(int uu , int vv){
for(int i = 1; i <= n; i++) vis[i] = 0 , dis[i] = 0x3ffffff;
queue<int> q;
dis[1] = 0;
vis[1] = 1;
q.push(1);
while(!q.empty()){
int x = q.front();
q.pop();
vis[x] = 0;
for(int i = 0; i < e[x].size(); i++){
int y = e[x][i].first , w = e[x][i].second;
if((x == uu && y == vv) || (x == vv && y == uu)) continue;
if(dis[y] > dis[x] + w){
dis[y] = dis[x] + w;
if(!vis[y]){
vis[y] = 1;
q.push(y);
}
}
}
}
ans = max(ans , dis[n]);
}
void p_work(){
for(int i = 1; i <= n; i++) vis[i] = 0 , dis[i] = 0x3ffffff;
queue<int> q;
dis[1] = 0;
vis[1] = 1;
q.push(1);
while(!q.empty()){
int x = q.front();
q.pop();
vis[x] = 0;
for(int i = 0; i < e[x].size(); i++){
int y = e[x][i].first , w = e[x][i].second;
if(dis[y] > dis[x] + w){
dis[y] = dis[x] + w;
pre[y] = x; //记录前驱
if(!vis[y]){
vis[y] = 1;
q.push(y);
}
}
}
}
ans = max(ans , dis[n]);
}
int main(){
scanf("%d%d" , &n , &m);
for(int i = 1; i <= m; i++){
int x , y , z;
scanf("%d%d%d" , &x , &y , &z);
e[x].push_back(make_pair(y , z));
e[y].push_back(make_pair(x , z));
}
p_work(); //预处理删哪些边
for(int i = n; i; i = pre[i]) work(i , pre[i]);
cout << ans;
return 0;
}
