首页 > 代码库 > BZOJ2763 JLOI2011 飞行路线 最短路
BZOJ2763 JLOI2011 飞行路线 最短路
题意：给定一张图，有可以将K条路径的花费变为0，求从1到N的最短路
题解：
分层图+最短路水过。
我们把原图复制K份，平行的放在一起（就像饼干一样一层层的），然后给每个图编号1 2 3……K，然后对于原图中每一条边(x,y)，在i的x和i+1的y之间连一条边权为0的边，然后在这K个图上做最短路即可。
当然这只是个思想，实际上你只需要多开一维记录在哪个层里即可，不用真的再去开N*(K-1)个点。
#include <queue>#include <cstdio>#include <climits>#include <cstring>#include <cstdlib>#include <iostream>#include <algorithm>using namespace std;#define NODE pair<int,int>const int MAXK=10+2;const int MAXN=10000+2;const int MAXM=50000+2;struct HASH{ int u,w; HASH *next; HASH(){} HASH(int _u,int _w,HASH *_next):u(_u),w(_w),next(_next){}}*table[MAXN*MAXK],mem[MAXM*2];int N,M,K,S,T,ans=INT_MAX,d[MAXN][MAXK],cnt;bool flag[MAXN][MAXK];queue<NODE> q;void Insert(int u,int v,int w){ table[u]=&(mem[cnt++]=HASH(v,w,table[u]));}void SPFA(int s){ memset(d,0X7F,sizeof(d)); q.push(make_pair(s,0)),flag[s][0]=1,d[s][0]=0; NODE x; while(!q.empty()){ x=q.front(),q.pop(); for(HASH *p=table[x.first];p;p=p->next){ if(d[p->u][x.second]>d[x.first][x.second]+p->w){ d[p->u][x.second]=d[x.first][x.second]+p->w; if(!flag[p->u][x.second]){ flag[p->u][x.second]=1; q.push(make_pair(p->u,x.second)); } } if(d[x.first][x.second]<d[p->u][x.second+1] && x.second<K){ d[p->u][x.second+1]=d[x.first][x.second]; if(!flag[p->u][x.second+1]){ flag[p->u][x.second+1]=1; q.push(make_pair(p->u,x.second+1)); } } } flag[x.first][x.second]=0; }}int main(){ scanf("%d %d %d %d %d",&N,&M,&K,&S,&T); for(int i=1,u,v,w;i<=M;i++){ scanf("%d %d %d",&u,&v,&w); Insert(u,v,w),Insert(v,u,w); } SPFA(S); for(int i=0;i<=K;i++) ans=min(ans,d[T][i]); printf("%d",ans); return 0;}
BZOJ2763 JLOI2011 飞行路线 最短路
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。