Time Limit: 4000MS | Memory Limit: 65536K | |
Total Submissions: 21084 | Accepted: 5740 |
Description
"Prince Remmarguts lives in his kingdom UDF – United Delta of Freedom. One day their neighboring country sent them Princess Uyuw on a diplomatic mission."
"Erenow, the princess sent Remmarguts a letter, informing him that she would come to the hall and hold commercial talks with UDF if and only if the prince go and meet her via the K-th shortest path. (in fact, Uyuw does not want to come at all)"
Being interested in the trade development and such a lovely girl, Prince Remmarguts really became enamored. He needs you - the prime minister's help!
DETAILS: UDF's capital consists of N stations. The hall is numbered S, while the station numbered T denotes prince' current place. M muddy directed sideways connect some of the stations. Remmarguts' path to welcome the princess might include the same station
twice or more than twice, even it is the station with number S or T. Different paths with same length will be considered disparate.
Input
sideway from A-th station to B-th station with time T.
The last line consists of three integer numbers S, T and K (1 <= S, T <= N, 1 <= K <= 1000).
Output
Sample Input
2 2 1 2 5 2 1 4 1 2 2
Sample Output
14
Source
#include<stdio.h> #include<iostream> #include<queue> #include<vector> using namespace std; #define inf 99999999 #define N 1100 typedef struct nnn { int F,G,s; friend bool operator<(nnn a,nnn b) { return a.F>b.F; } }PATH; typedef struct nn { int v,w; }node; vector<node>map[N],tmap[N]; int H[N]; void findH(int s) { queue<int>q; int inq[N]={0}; q.push(s); inq[s]=1; H[s]=0; while(!q.empty()) { s=q.front(); q.pop(); inq[s]=0; int m=tmap[s].size(); for(int i=0;i<m;i++) { int j=tmap[s][i].v; if(H[j]>tmap[s][i].w+H[s]) { H[j]=tmap[s][i].w+H[s]; if(!inq[j]) inq[j]=1,q.push(j); } } } } int Astar(int st,int end,int K) { priority_queue<PATH>q; PATH p,tp; int k[N]={0}; findH(end); if(H[st]==inf)return -1; p.s=st; p.G=0; p.F=H[st]; q.push(p); while(!q.empty()) { p=q.top(); q.pop(); k[p.s]++; if(k[p.s]>K)continue;//每个点最多走K次,超过K条路不必走 if(p.s==end&&k[end]==K) return p.F; int m=map[p.s].size(); for(int i=0;i<m;i++) { int j=map[p.s][i].v; if(H[j]!=inf)//表明当前点不能通向终点,就不用加入队列 { tp.G=p.G+map[p.s][i].w; tp.F=H[j]+tp.G; tp.s=j; q.push(tp); } } } return -1; } int main() { int n,m,S,T,K,a,b,t; node p; scanf("%d%d",&n,&m); for(int i=1;i<=n;i++) { map[i].clear(); tmap[i].clear(); H[i]=inf; } while(m--) { scanf("%d%d%d",&a,&b,&t); p.v=b; p.w=t; map[a].push_back(p); p.v=a; tmap[b].push_back(p);//反建一个地图求H } scanf("%d%d%d",&S,&T,&K); if(S==T)K++; printf("%d\n",Astar(S,T,K)); }