HDU6797 Tokitsukaze and Rescue（Dijkstra）

HDU6797 Tokitsukaze and Rescue（Dijkstra）

Description
Princess CJB has lived almost her entire life in the isolated town of Ertona, where CJB uses her unique ability to recognize where crystals of materials are buried. By way of a fateful encounter, CJB learns of the Alchemy Exam and decides to take her first step into the outside world, setting off on a grand journey to become a certified alchemist and discover the mysteries that life has to offer!
In order to take part in the Alchemy Exam, CJB goes to the Reisenberg town without any partners. But the kingdom Adalet is unbelievably enormous so that there are many hidden risks. Claris, a powerful evil magician, wants to monopolize CJB for the extraordinary beauty of her. Due to the power limitation of CJB, she can’t escape from Claris without any assistance. The alchemist Tokitsukaze has heard this savage act and wants to rescue the princess CJB.
There are n cities numbered from 1 to n in the kingdom Adalet. Because of the excellent transportation, there is exactly a two-way road between any two cites. Tokitsukaze lives in city 1. The Magician Claris lives in city n. Since the exam will be held soon, Tokitsukaze wants to rescue CJB as fast as possible, so she will choose the shortest path to reach city n.
Claris has also heard this news and is afraid of being punished, so he decides to slow Tokitsukaze down by making an explosion on k roads he chose and causing these roads to lose their capability of two-way transportation, since it can pave the way for having enough time to prepare his powerful magic against Tokitsukaze.
Tokitsukaze knows some roads will be destroyed and can immediately recognize where they are, but she has no approach to prevent this explosion, so she chooses just to move along the shortest path after Claris completes his explosion.
Now Claris wants to know, after finishing his explosion, what the longest possible length is of the shortest path from city 1 to city n.
Input
There are several test cases.
The first line contains an integer T (1≤T≤100), denoting the number of test cases. Then follow all the test cases.
For each test case, the first line contains two integers n and k (3≤n≤50,1≤k≤min(n−2,5)), denoting the number of cities and the number of roads being exploded, respectively.
The next n(n−1)2 lines describe all the roads, where each line contains three integers u, v and w (1≤u,v≤n,u≠v,1≤w≤104), representing a two-way road of length w between city u and city v. It is guaranteed that for every two cities, there exists exactly one road whose length is randomly distributed between 1 and 104.
Output
For each case, output in one line an integer, denoting the longest possible length of the shortest path after the explosion.
Sample Input
3
5 1
1 2 2990
1 3 2414
1 4 4018
1 5 6216
2 3 9140
2 4 4169
2 5 550
3 4 6618
3 5 3206
4 5 105
5 2
1 2 2990
1 3 2414
1 4 4018
1 5 6216
2 3 9140
2 4 4169
2 5 550
3 4 6618
3 5 3206
4 5 105
5 3
1 2 2990
1 3 2414
1 4 4018
1 5 6216
2 3 9140
2 4 4169
2 5 550
3 4 6618
3 5 3206
4 5 105
Sample Output
4123
5620
6216

题意

给出n个点，n*(n-1)/2条边。从边中随机删去k条，问最短路中最大的是多少。
很奇葩，给了8秒钟，k又小于等于5，所以直接爆搜就好了，Dij套Dij。而且n最多只有50，所以用邻接矩阵存图就好了。
分别枚举最短路中的k个边删除，然后计算最短路。具体代码中，删除边的操作是通过递归实现的。删除点的方式，就是将邻接矩阵中的权值赋值为INF（记得是双向图，正反都要赋值为INF）。
温哥哥不用优先队列的写法比我整整快了4s，太强了。

#include<iostream>#include<string>#include<cstring>#include<cmath>#include<cstdio>#include<queue>#include<stack>#include<vector>#include<algorithm>#include<functional>#include<map>#include<unordered_map>#define lowbit(x) ((x)&-(x))using namespace std;typedef long long ll;typedef unsigned long long ull;const ll N=1e6+10,NN=2e3+10,INF=0x3f3f3f3f,LEN=20;const ll MOD=1e9+7;const ull seed=31;inline ll read(){ll x=0,f=1;char ch=getchar();while(ch<\'0\'||ch>\'9\'){if(ch==\'-\') f=-1;ch=getchar();}while(ch>=\'0\'&&ch<=\'9\'){x=(x<<1)+(x<<3)+(ch^48);ch=getchar();}return x*f;}struct Node{ll id;ll dis;Node(ll v,ll w):id(v),dis(w){}bool friend operator<(const Node &a,const Node &b){return a.dis>b.dis;}};ll n,k,sum,maxx;ll pre[NN][NN],dis[NN];ll mp[NN][NN];bool done[NN];void dijkstra(ll cnt){if(cnt==k+2){maxx=max(maxx,dis[n]);return ;}ll s=1;for(ll i=1;i<=n;i++){dis[i]=INF;done[i]=false;}dis[s]=0;priority_queue<Node>q;q.push(Node(s,dis[s]));while(!q.empty()){Node u=q.top();q.pop();if(done[u.id]) continue;done[u.id]=true;for(ll j=1;j<=n;j++){if(mp[u.id][j]!=INF){if(done[j]) continue;if(dis[j]>mp[u.id][j]+u.dis){dis[j]=mp[u.id][j]+u.dis;q.push(Node(j,dis[j]));pre[cnt][j]=u.id;//用二维数组记录路径，cnt表示删除了cnt-1个点的循环}}}}for(int i=n;i!=1;i=pre[cnt][i]){ll temp=mp[i][pre[cnt][i]];mp[i][pre[cnt][i]]=mp[pre[cnt][i]][i]=INF;//删除边dijkstra(cnt+1);//删除这条边后进入下一个循环mp[i][pre[cnt][i]]=mp[pre[cnt][i]][i]=temp;//记得还原，因为不一定删除这个边就能得到最优解，画个样例模拟琢磨就可以了}}void init(){sum=0;memset(mp,INF,sizeof mp);memset(pre,-1,sizeof pre);}int main(){ll t;scanf(\"%lld\",&t);while(t--){init();scanf(\"%lld%lld\",&n,&k);for(ll i=1;i<=(n*(n-1))/2;i++){ll u,v,w;scanf(\"%lld%lld%lld\",&u,&v,&w);mp[u][v]=w;mp[v][u]=w;}maxx=-INF;dijkstra(1);printf(\"%lld\\n\",maxx);}}