bzoj2763 jloi2011飞行路线

网友投稿 815 2022-08-29

bzoj2763 jloi2011飞行路线

bzoj2763 jloi2011飞行路线

​​ Description

Alice和Bob现在要乘飞机旅行,他们选择了一家相对便宜的航空公司。该航空公司一共在n个城市设有业务,设这些城市分别标记为0到n-1,一共有m种航线,每种航线连接两个城市,并且航线有一定的价格。Alice和Bob现在要从一个城市沿着航线到达另一个城市,途中可以进行转机。航空公司对他们这次旅行也推出优惠,他们可以免费在最多k种航线上搭乘飞机。那么Alice和Bob这次出行最少花费多少?

Input

数据的第一行有三个整数,n,m,k,分别表示城市数,航线数和免费乘坐次数。

第二行有两个整数,s,t,分别表示他们出行的起点城市编号和终点城市编号。(0<=s,t

#include#include#include#includeusing namespace std;#define pa pair >#define N 11000#define M 55000inline int read(){ int x=0;char ch=getchar(); while (ch<'0'||ch>'9') ch=getchar(); while (ch<='9'&&ch>='0') {x=x*10+ch-'0';ch=getchar();} return x;}struct node{ int y,z,next;}data[M<<1];bool flag[N][15];int f[N][15],h[N],n,m,k,S,T,num;inline int min(int x,int y){ return x,greater >q; q.push(make_pair(0,make_pair(S,0))); memset(f,0x7f,sizeof(f));f[S][0]=0; while (!q.empty()){ int x=q-().second.first,level=q-().second.second;q.pop(); if (flag[x][level]) continue;else flag[x][level]=true; for (int i=h[x];i;i=data[i].next){ int y=data[i].y,z=data[i].z; if (f[x][level]+z

版权声明:本文内容由网络用户投稿,版权归原作者所有,本站不拥有其著作权,亦不承担相应法律责任。如果您发现本站中有涉嫌抄袭或描述失实的内容,请联系我们jiasou666@gmail.com 处理,核实后本网站将在24小时内删除侵权内容。

上一篇:14 个实用的数据库设计技巧,哪些你还不知道?
下一篇:bzoj1491&luogu2047
相关文章

 发表评论

暂时没有评论,来抢沙发吧~