2 2
1 2 5
2 1 4
1 2 2
题目大意就是给出一个图,然后给出一个起点个一个终点,求这两点间的第K短路。
本题中是可以走重复的路的,所以如果一张图中有一个环的话,无论求第几短路都存在。
思路:前向星+SPFA+A*
LANGUAGE:C++
CODE:
#include <cstring>
#include <cstdio>
#include <queue>
#define MAXN 1005
#define MAXM 500005
#define INF 1000000000
using namespace std;
struct node
{
int v, w, next;
}
edge[MAXM], revedge[MAXM];
struct A
{
int f, g, v;
bool operator <(const A a)
const
{
if(a.f == f) return a.g < g;
return a.f < f;
}
};
int e, vis[MAXN], d[MAXN], q[MAXM * 5];
int
head[MAXN], revhead[MAXN];
int n, m, s, t, k;
void init()
{
e = 0;
memset(head, -1, sizeof(head));
memset(revhead, -1, sizeof(revhead));
}
void insert(int x, int y, int w)
{
edge[e].v = y;
edge[e].w = w;
edge[e].next = head[x];
head[x] = e;
revedge[e].v = x;
revedge[e].w = w;
revedge[e].next =revhead[y];
revhead[y] = e++;
}
void spfa(int src)
{
for(int i = 1; i <= n; i++) d[i] = INF;
memset(vis, 0, sizeof(vis));
vis[src] = 0;
int h = 0, t = 1;
q[0] = src;
d[src] = 0;
while(h < t)
{
int u =
q[h++];
vis[u] = 0;
for(int i = revhead[u] ; i != -1; i = revedge[i].next)
{
int v = revedge[i].v;
int w = revedge[i].w;
if(d[v] > d[u] + w)
{
d[v] = d[u] + w;
if(!vis[v])
{
q[t++] = v;
vis[v] = 1;
}
}
}
}
}
int Astar(int src, int des)
{
int cnt = 0;
priority_queue<A>Q;
if(src == des) k++;
if(d[src] == INF) return -1;
A t, tt;
t.v = src, t.g = 0, t.f = t.g + d[src];
Q.push(t);
while(!Q.empty())
{
tt = Q.top();
Q.pop();
if(tt.v == des)
{
cnt++;
if(cnt == k) return tt.g;
}
for(int i = head[tt.v]; i != -1; i = edge[i].next)
{
t.v = edge[i].v;
t.g = tt.g + edge[i].w;
t.f = t.g + d[t.v];
Q.push(t);
}
}
return -1;
}
int main()
{
int x, y, w;
while(scanf("%d%d", &n, &m) != EOF)
{
init();
for(int i = 1; i <= m; i++)
{
scanf("%d%d%d", &x, &y, &w);
insert(x, y, w);
}
scanf("%d%d%d", &s, &t, &k);
spfa(t);
printf("%d\n", Astar(s, t));
}
return 0;
}
相关推荐
East Central North America 1999。50字50字50字50字50字50字50字50字50字50字50字50字50字50字50字50字50字50字50字50字50字50字50字50字50字50字50字50字50字50字50字50字50字50字50字50字50字50字50字50字50字50...
POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类
poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题...
POJ第1861题源码 POJ第1861题源码 POJ第1861题源码
北大POJ1159-Palindrome 解题报告+AC代码
C语言 poj npu 西工大 C语言Poj答案全完整打包,给有需要的朋友
poj 3414解题报告poj 3414解题报告poj 3414解题报告poj 3414解题报告
poj分类poj分类poj分类poj分类
poj 1012解题报告poj 1012解题报告poj 1012解题报告poj 1012解题报告
北大POJ2002-Squares 解题报告+AC代码
poj 2329解题报告poj 2329解题报告poj 2329解题报告poj 2329解题报告
POJ1503解答 POJ1503解答,正确答案(已通过POJ)
POJ1048,加强版的约瑟夫问题 难度中等
poj 1659解题报告poj 1659解题报告poj 1659解题报告poj 1659解题报告
POJ1083的代码,POJ1083的代码,POJ1083的代码
poj 百练 题目分类 poj 百练 题目分类
POJ上的一道题目,自己写的代码,因为想下载别人的, 所以就放上了。
Poj中一些题目的源代码,里面共有二十多道题目,OI
POJ2968代码有用,欢迎下载,POJ代码
poj 1001答案