本文主要是介绍poj 2449 Remmarguts' Date（K短路,A*算法），希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
http://poj.org/problem?id=2449
大致题意：给出一个有向图，求从起点到终点的第K短路。
K短路与A*算法详解 学长的博客。。。
算法过程
#include <stdio.h>
#include <iostream>
#include <algorithm>
#include <set>
#include <map>
#include <vector>
#include <math.h>
#include <string.h>
#include <queue>
#include <string>
#define LL long long
#define _LL __int64
using namespace std;
const int INF = 0x3f3f3f3f;
const int maxn = 1010;
const int maxm = 100010;struct node
{int u,v,w;
};int s,t,k;
int n,m;
vector <struct node> edge[maxn],edge1[maxn]; //邻接表存图以及反向图
int dis[maxn]; // 终点到所有点的最短路
int time[maxn];// 每个点的出队列次数
int ans;bool operator > (const struct node &a, const struct node &b)
{return a.w+dis[a.v] > b.w + dis[b.v];
}
priority_queue < node, vector<node>, greater<node> >q;void init()
{for(int i = 1; i <= n; i++){edge[i].clear();edge1[i].clear();}
}//spfa求终点到其他左右点的最短路
void spfa()
{int inque[maxn];queue<int> que;while(!que.empty()) que.pop();memset(inque,0,sizeof(inque));memset(dis,INF,sizeof(dis));dis[t] = 0;inque[t] = 1;que.push(t);while(!que.empty()){int u = que.front();que.pop();inque[u] = 0;for(int i = 0; i < (int)edge1[u].size(); i++){int v = edge1[u][i].v;int w = edge1[u][i].w;if(dis[v] > dis[u] + w){dis[v] = dis[u] + w;if(!inque[v]){inque[v] = 1;que.push(v);}}}}
}void solve()
{while(!q.empty()) q.pop();memset(time,0,sizeof(time));struct node tmp;bool flag = false;//起点进队列tmp.v = s;tmp.w = 0;q.push(tmp);while(!q.empty()){struct node u = q.top();q.pop();time[u.v]++;if(time[u.v] >= k) //出队次数大于等于K时{if(u.v == t) //如果是终点，判断与起点是否相同//若不相同,当前值便是第K短路，否则第K+1次才是最短路{if(t != s || (t == s && time[u.v] == k+1)){flag = true;ans = u.w;break;}}if(time[u.v] > k)//如果不是终点，当出队次数大于K次就不再进队列continue;}int now = u.v;for(int i = 0; i < (int)edge[now].size(); i++){struct node tmp;tmp.v = edge[now][i].v;tmp.w = u.w + edge[now][i].w;q.push(tmp);}}if(!flag)ans = -1;
}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);edge[u].push_back( (struct node){u,v,w} );edge1[v].push_back( (struct node) {v,u,w} );}scanf("%d %d %d",&s,&t,&k);spfa();solve();printf("%d\n",ans);}return 0;
}
这篇关于poj 2449 Remmarguts' Date（K短路,A*算法）的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
