本文主要是介绍Remmarguts' Date POJ - 2449，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
点击打开链接
K短路 存模板
#include <cstdio>
#include <queue>
#include <cstring>
#include <algorithm>
using namespace std;
#define N 0x3f3f3f3fint dis[1010];struct node1
{int v;int w;int next;
};struct node2
{bool operator < (const node2 &rhs) const{return val + dis[id] > rhs.val + dis[rhs.id];}int id;int val;
};priority_queue <node2> que;
node1 edge1[200010],edge2[200010];
int first1[1010],first2[1010],book[1010];
int n,m,num,s,e,k;void addedge(node1* edge,int* first,int u,int v,int w)
{edge[num].v=v;edge[num].w=w;edge[num].next=first[u];first[u]=num++;return;
}void dijkstra()
{node2 cur,tem;int i,u,v,w;while(!que.empty()) que.pop();memset(dis,0x3f,sizeof(dis));memset(book,0,sizeof(book));tem.id=e,tem.val=0;que.push(tem);dis[e]=0;while(!que.empty()){cur=que.top();que.pop();u=cur.id;if(book[u]) continue;book[u]=1;for(i=first2[u];i!=-1;i=edge2[i].next){v=edge2[i].v,w=edge2[i].w;if(!book[v]&&dis[v]>dis[u]+w){dis[v]=dis[u]+w;tem.id=v,tem.val=dis[v];que.push(tem);}}}return;
}int astar()
{node2 cur,tem;int i,u,v,w;while(!que.empty()) que.pop();tem.id=s,tem.val=0;que.push(tem);k--;while(!que.empty()){cur=que.top();que.pop();u=cur.id;if(u==e){if(k>0) k--;else return cur.val;}for(i=first1[u];i!=-1;i=edge1[i].next){v=edge1[i].v,w=edge1[i].w;tem.id=v,tem.val=cur.val+w;que.push(tem);}}return -1;
}int main()
{int i,u,v,w;while(scanf("%d%d",&n,&m)!=EOF){memset(first1,-1,sizeof(first1));memset(first2,-1,sizeof(first2));num=0;for(i=1;i<=m;i++){scanf("%d%d%d",&u,&v,&w);addedge(edge1,first1,u,v,w);addedge(edge2,first2,v,u,w);}scanf("%d%d%d",&s,&e,&k);dijkstra();if(dis[s]==N){printf("-1\n");continue;}if(s==e) k++;printf("%d\n",astar());}return 0;
}
这篇关于Remmarguts' Date POJ - 2449的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
