题意：给出一个完全图，求删除K边后，最长的最短路径。
题解：删除的边肯定要在最短路径上删除，删除一条边后，跑一次最短路径，在从最短路径上暴力选择一个删除，直到删了K条边。注意ans要初始化，还有就是最短路径数组是二维的，开滚动数组在dfs的过程中被迭代掉。
#include <bits/stdc++.h> #define IO_read ios::sync_with_stdio(false);cin.tie(0) #define fre freopen("in.txt", "r", stdin) #define _for(i,a,b) for(int i=a; i< b; i++) #define _rep(i,a,b) for(int i=a; i<=b; i++) #define inf 0x3f3f3f3f #define lowbit(a) ((a)&-(a)) using namespace std; typedef long long ll; template <class T> void read(T &x) { char c; bool op=0; while(c=getchar(), c<'0'||c>'9') if(c=='-') op=1; x=c-'0'; while(c=getchar(), c>='0'&&c<='9') x=x*10+c-'0'; if(op) x=-x; } template <class T> void write(T x) { if(x<0) putchar('-'), x=-x; if(x>=10) write(x/10); putchar('0'+x%10); } const int maxn=55, maxm=2505; int T, n, k; struct qnode{ int v, c; qnode(int _v=0, int _c=0):v(_v), c(_c) {} bool operator <(const qnode &r) const{ return c>r.c; } }; struct Edge{ int v, cost; Edge(int _v=0, int _cost=0): v(_v), cost(_cost) {} }; vector<Edge> E[maxn]; int vis[maxn], pre[maxn][maxn]; int dis[maxn], val[maxn][maxn]; void dijkstra(int deep, int start) { for(int i=1; i<=n; i++) dis[i]=inf, vis[i]=0; priority_queue<qnode> que; que.push(qnode(start, 0)); dis[start]=0; while(!que.empty()) { qnode tmp=que.top(); que.pop(); int u=tmp.v; if(vis[u]) continue; vis[u]=true; for(int i=0; i<E[u].size(); i++) { int v=E[u][i].v; int cost=val[u][v]; if(!vis[v] && dis[v]>dis[u]+cost) { dis[v]=dis[u]+cost; pre[deep][v]=u; que.push(qnode(v, dis[v])); } } } } int ans; void del(int x) { dijkstra(x, 1); if(!x){ if(dis[n]!=inf) ans=max(ans, dis[n]); return; } for(int i=n; pre[x][i]; i=pre[x][i]) { int j=pre[x][i]; int w=val[i][j]; val[i][j]=val[j][i]=inf; del(x-1); val[i][j]=val[j][i]=w; } } int main() { //fre; read(T); while(T--) { read(n), read(k); for(int i=1; i<=n; i++) E[i].clear(); for(int i=1; i<=n; i++) for(int j=1; j<=n; j++) val[i][j]= i==j? 0:inf; for(int i=1; i<=n*(n-1)/2; i++) { int u, v, w; read(u), read(v); read(w); E[u].push_back(Edge(v, w)); E[v].push_back(Edge(u, w)); val[u][v]=val[v][u]=w; } ans=-inf; del(k); printf("%d ", ans); } return 0; }