本文同步更新于洛谷博客

题目描述

给定一张 \(n\) 个点 \(m\) 条边的带权无向图，求删除一条边后，最短路的最大值。

题解

不难发现，如果删除的边不在原图的最短路上，对结果是没有影响的。因此我们要先跑一边最短路，用 \(pre\) 数组记录下原图最短路上的每一个点。接着我们暴力枚举将每一条边删除后的最短路，取最大值即可。然后我们开开心心的交上去，发现 TLE 了。
所以我们需要优化，但是不会线段树优化怎么办？不会斐波那契堆怎么办？没关系，我们可以用 clock 函数来控制程序运行的时间，在快要超时的时候输出最优解即可。

Code

#include
using namespace std;
const int maxn=1005; 
int n,m,g[maxn][maxn],dis[maxn],minn,k,ans,x,y;
bool vis[maxn],flag;
int pre[maxn];
int min(int a,int b)
{
    return a