题目链接：http://poj.org/problem?id=2449
题意 题目的意思很明确，就是让你求s到t的第k短路。不过有一个trick点就是必须要经过路径，也就是说如果s=t的话，在算第k短路时不能算s到t为0这条路。
题解 基本就是裸的第k短路，而第k短路是单源最短路和A*算法的组合。对于A*算法，都知道f(n)=g(n)+h(n)，这里h(n)为启发式函数。我们令这里的g(n)为从源点s到n所经过的路径，h(n)为把所有边反向后从终点t到n的最短路径dist[n]。即估值=源点到当前点的距离+当前点到终点的最短距离。这时我们建一个优先队列，每次弹出估值f()最小的点，如果弹出的点是t就计算t出队的次数，如果次数等于k，那么到当前点的距离g()即为答案，否者就拓展与当前点相连的边。
#include <cstdio> #include <cstdlib> #include <queue> #include <iostream> #include <cstring> using namespace std; #define INF 0x3f3f3f3f typedef long long ll; const int maxn = 1e3+5; const int maxm = 1e5+5; int n,m,s,t,k,ans; //前向星储存边 int head[maxn],A_head[maxn],cnt1,cnt2; //dist[]储存终点到其它点的最短路 int dist[maxn]; struct Edge{ int to,w,next; }edge1[maxm],edge2[maxm]; struct A_Node{ int p,g,h; bool operator < (A_Node tmp) const { return tmp.g+tmp.h < g+h; } }; typedef pair<int,int> P; void init() { memset(head,-1,sizeof(head)); memset(A_head,-1,sizeof(A_head)); memset(dist,INF,sizeof(dist)); cnt1=cnt2=0; } void add_edge(int from,int to,int w,bool flag) { if(flag) { edge1[cnt1].to = to; edge1[cnt1].w = w; edge1[cnt1].next = head[from]; head[from] = cnt1++; } else { edge2[cnt2].to = to; edge2[cnt2].w = w; edge2[cnt2].next = A_head[from]; A_head[from] = cnt2++; } } void Dijkstra() //优先队列优化的Dijkstra求终点到其它点的最短路 { priority_queue<P,vector<P>,greater<P> >pq; P p; dist[t] = 0; pq.push(P(0,t)); while(!pq.empty()) { p = pq.top(),pq.pop(); int u = p.second; for(int i=head[u];i!=-1;i=edge1[i].next) { if(dist[edge1[i].to] > dist[u] + edge1[i].w) { dist[edge1[i].to] = dist[u]+edge1[i].w; pq.push(P(dist[edge1[i].to],edge1[i].to)); } } } } void A_stra() { A_Node cur,next; int num=0; priority_queue<A_Node>pq; //源点为终点，不去掉为0的路径就相当于求第k+1短路 if(s==t) k++; if(dist[s]==INF) { ans=-1; return; } cur.p = s; cur.g = 0; cur.h = dist[s]; pq.push(cur); while(!pq.empty()) { cur = pq.top(),pq.pop(); if(cur.p==t) num++; if(num==k) { ans = cur.g; return; } for(int i=A_head[cur.p];i!=-1;i=edge2[i].next) { next.p = edge2[i].to; next.g = cur.g+edge2[i].w; next.h = dist[next.p]; pq.push(next); } } ans = -1; return; } int main() { while(~scanf("%d%d",&n,&m)) { init(); int u,v,w; for(int i=1;i<=m;i++) { scanf("%d%d%d",&u,&v,&w); add_edge(v,u,w,true); add_edge(u,v,w,false); } scanf("%d%d%d",&s,&t,&k); Dijkstra(); A_stra(); printf("%d\n",ans); } return 0; }