题目链接：http://poj.org/problem?id=2449
题意是n个点，m条边，然后输入m条边，最后输入起始点和终止点和第k短路。
是一个k短路的模板题(赤裸裸的)，呆码也可以存下来当模板用，主要是spfa A*实现的。
AC代码：
代码语言：javascript复制#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <queue>
#define maxn 1100
#define maxm 110000
#define inf 0xffffff0
using namespace std;
struct Node{
int to,w,next;
}Edge[maxm],Edge1[maxm];
int head[maxn],head1[maxn];
struct node{
int to,g,f;
bool operator < (const node &a) const{
if(a.f == f){
return a.g < g;
}
return a.f < f;
}
};
int dist[maxn];
bool vis[maxn];
int n,m,s,t,k;
void init(){
memset(Edge,0,sizeof(Edge));
memset(Edge1,0,sizeof(Edge1));
memset(head,-1,sizeof(head));
memset(head1,-1,sizeof(head1));
}
void spfa(int s){
for(int i=0;i<=n;i ){
dist[i] = inf;
}
memset(vis,false,sizeof(vis));
vis[s] = 1;
dist[s] = 0;
queue<int> q;
q.push(s);
while(!q.empty()){
int u = q.front();
q.pop();
vis[u] = false;
for(int i=head1[u];i!=-1;i=Edge1[i].next){
int ans = dist[u] Edge1[i].w;
if(ans < dist[Edge1[i].to]){
dist[Edge1[i].to] = ans;
if(!vis[Edge1[i].to]){
vis[Edge1[i].to] = 1;
q.push(Edge1[i].to);
}
}
}
}
}
int A_Star(){
node e,ne;
int cnt = 0;
priority_queue<node> q;
if(s == t) k ;
if(dist[s] == inf) return -1;
e.to = s;
e.g = 0;
e.f = e.g dist[e.to];
q.push(e);
while(!q.empty()){
e = q.top();
q.pop();
if(e.to == t) cnt ;
if(cnt == k) return e.g;
for(int i=head[e.to];i!=-1;i=Edge[i].next){
ne.to = Edge[i].to;
ne.g = e.g Edge[i].w;
ne.f = ne.g dist[ne.to];
q.push(ne);
}
}
return -1;
}
int main()
{
while(~scanf("%d%d",&n,&m)){
init();
for(int i=0;i<m;i ){
int u,v,w;
scanf("%d%d%d",&u,&v,&w);
Edge[i].to = v;
Edge[i].w = w;
Edge[i].next = head[u];
head[u] = i;
Edge1[i].to = u;
Edge1[i].w = w;
Edge1[i].next = head1[v];
head1[v] = i;
}
scanf("%d%d%d",&s,&t,&k);
spfa(t);
int ans = A_Star();
printf("%dn",ans);
}
return 0;
}
