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小时内删除侵权内容。