题意:
再次成功营救出桃子公主之后，马里奥需要从Bowser魔王的城堡返回他的家。马里奥世界里一共有A个村庄和B个城堡（1<=A,B<=50），其中村庄编号为1到A，城堡编号为A+1到A+B。马里奥住在村庄1，而Bowser住在城堡A+B。
马里奥能以1公里/小时的速度沿着村庄和城堡之间的双向道路行走，也可以用魔法鞋加速。魔法鞋可以让马里奥瞬间移动不超过L（L<=50）公里，但由于城堡中有很多陷阱，稍不留神就会中招，因此马里奥不使用魔法鞋穿过城堡。另外，使用魔法鞋的起点和终点都只能是城堡或者村庄，且最多只能使用K（K<=10）次魔法鞋。 你的任务是计算马里奥回家的最短时间。输入保证马里奥一定能回家。
分析:不使用魔法鞋穿过城堡没看懂啊啊啊啊啊啊啊,,理解能力太弱了!!!
因为不使用魔法鞋穿过城堡,所有算最短路时,中间结点不能是城堡!先用floyd算法,将每个点使用魔法鞋能去的地方算出来(先不考虑距离约束).
接下来就是dijkstra算法,算出A+B点到1点所花费的最短时间,因为可以使用K次魔法,故每个点的状态是K+1次,V[u][k]是指A+B到达u点,还有k次魔法没用使用花费的时间..
然后用优先队列,最先出来的终点所花费的时间即是答案!
// File Name: 10269.cpp // Author: Zlbing // Created Time: 2013/4/16 22:04:15 #include<iostream> #include<string> #include<algorithm> #include<cstdlib> #include<cstdio> #include<set> #include<map> #include<vector> #include<cstring> #include<stack> #include<cmath> #include<queue> using namespace std; #define CL(x,v); memset(x,v,sizeof(x)); #define INF 0x3f3f3f3f #define LL long long #define REP(i,r,n) for(int i=r;i<=n;i++) #define RREP(i,n,r) for(int i=n;i>=r;i--) const int MAXN=105; int A,B,M,L,K; struct node { int u,cost,k; bool operator <(const node& a)const { return cost>a.cost; } }; int G[MAXN][MAXN]; int V[MAXN][MAXN]; void floyd() { for(int k=1; k<=A; k++) for(int i=1; i<=A+B; i++) for(int j=1; j<=A+B; j++) { if(G[i][k]+G[k][j]<G[i][j]) G[i][j]=G[i][k]+G[k][j]; } } int dijkstra() { CL(V,-1); priority_queue<node>Q; node a; a.u=A+B; a.cost=0; a.k=K; Q.push(a); REP(i,0,K) V[A+B][i]=0; while(!Q.empty()) { node t=Q.top(); Q.pop(); int u=t.u; int cost=t.cost; int k=t.k; if(u==1)return cost; node tt; for(int i=1; i<=A+B; i++) { if(G[u][i]!=INF&&u!=i) { if(G[u][i]<=L&&(V[i][k-1]==-1||V[i][k-1]>cost)&&k>0) { V[i][k-1]=cost; tt.u=i; tt.cost=cost; tt.k=k-1; // printf("--a----\n"); // printf("u%d cost%d k%d\n",tt.u,tt.cost,tt.k); Q.push(tt); } if(V[i][k]==-1||V[i][k]>cost+G[u][i]) { V[i][k]=cost+G[u][i]; tt.u=i; tt.cost=cost+G[u][i]; tt.k=k; // printf("--a----\n"); // printf("u%d cost%d k%d\n",tt.u,tt.cost,tt.k); Q.push(tt); } } } } return -1; } int main() { int T; scanf("%d",&T); while(T--) { scanf("%d%d%d%d%d",&A,&B,&M,&L,&K); REP(i,1,A+B) REP(j,1,A+B) G[i][j]=INF; REP(i,1,M) { int a,b,c; scanf("%d%d%d",&a,&b,&c); G[a][b]=c; G[b][a]=c; } floyd(); int ans=dijkstra(); printf("%d\n",ans); } return 0; }