典型的求k短路径的问题,有很多种算法,暂时试了试Dijkstra+A*算法
k短路径的相关问题看这里,尽管已经是2007年的文章了,但作者真的写得非常详细和全面。
下面是一个简化的算法流程。
/* * k短路径 Dijkstra+A*算法 * 算法流程: * 1.将有向图的边反向后,Dijkstra求出任意节点到终点的最短路径 dis[i] * 2.优先队列 * struct * { * int v,l,d; * }priority_queue[10000]; * v:结点编号 * l:源点到v的距离 * d:源点经过v的到终点的某一条路径的长度 * 优先队列以l为权值排序 * 3.v = s,l = 0,d = 0; 入队 * 每次从优先队列中取出并去除l最小的结点 * 遍历结点v的所有后继,计算d,l并入队,不判断v的后继结点是否在队列中 for(i=head[k];i;i=edge[i].next) { q[++len].v = edge[i].v; q[len].d = dis[edge[i].v]+edge[i].d+q[l].l; q[len].l = q[l].l+edge[i].d; inq[len] = true; sum++; } * 4.第k次取出终点结点t,d即为第k短路径 * 可能出现同一长度的不同路径,都会被分别找出 * */
/* * poj2449 AC * k短路径 Dijkstra+A*算法 266ms * 第一次用STL,还不是很熟悉,以前都是手写二叉堆的。 * Dijkstra开始写错了,导致TLE,一天不写手生。 * 题目要注意,当终点和起点相同时,最短路径不是0,必须走一圈回来。 * */ #include<stdio.h> #include<memory.h> #include<queue> #include<fstream> #include<vector> using namespace std; #define INF 100000000 struct EDGE { int v,t; long next; }edge[100005],e[100005]; typedef struct { long len,d; int v; }NODE; struct cmp { bool operator()(const NODE &t1,const NODE &t2) { return t1.d>t2.d; } }; long head[1005],h[1005]; long n,m,tot,tot1; int a,b,c; long dis[1005]; void Dijkstra() { bool vis[1005]; NODE node,tmp; priority_queue<NODE,vector<NODE>,cmp> queue; long i,j; for(i=1;i<=n;i++) { vis[i] = false; dis[i] = INF; } dis[b] = 0; node.d= 0,node.v = b; queue.push(node); for(i=1;i<=n;i++) { node = queue.top(); queue.pop(); vis[node.v] = true; for(j=h[node.v];j;j=e[j].next) if(!vis[e[j].v] && dis[e[j].v]>dis[node.v]+e[j].t) { dis[e[j].v] = dis[node.v]+e[j].t; tmp.v = e[j].v; tmp.d= dis[e[j].v]; queue.push(tmp); } } while(!queue.empty()) queue.pop(); return; } long a_star() { NODE node,tmp; long i,num = 0; priority_queue<NODE,vector<NODE>,cmp> queue; node.len = 0,node.d = 0,node.v = a; queue.push(node); while(!queue.empty()) { node = queue.top(); queue.pop(); if(node.v==b) { num++; if(num==c) return node.d; } for(i=head[node.v];i;i=edge[i].next) { tmp.v = edge[i].v; tmp.d = node.len+edge[i].t+dis[edge[i].v]; tmp.len = node.len+edge[i].t; queue.push(tmp); } } return -1; } int main() { // FILE* fin; // fin = fopen("d.in","r"); scanf("%ld%ld",&n,&m); // fscanf(fin,"%ld%ld",&n,&m); int i,j,k,t; memset(head,0,sizeof(head)); memset(h,0,sizeof(h)); tot = tot1 = 0; for(i=1;i<=m;i++) { scanf("%d%d%d",&j,&k,&t); // fscanf(fin,"%d%d%d",&j,&k,&t); edge[++tot].v = k,edge[tot].t = t,edge[tot].next = head[j],head[j] = tot; e[++tot1].v = j,e[tot1].t = t,e[tot1].next = h[k],h[k] = tot1; } scanf("%d%d%d",&a,&b,&c); // fscanf(fin,"%d%d%d",&a,&b,&c); if(a==b) c++; Dijkstra(); long ans; ans = a_star(); printf("%ld\n",ans); return 0; }