题目描述
Alice和Bob现在要乘飞机旅行，他们选择了一家相对便宜的航空公司。该航空公司一共在nn个城市设有业务，设这些城市分别标记为00到n-1n−1，一共有mm种航线，每种航线连接两个城市，并且航线有一定的价格。
Alice和Bob现在要从一个城市沿着航线到达另一个城市，途中可以进行转机。航空公司对他们这次旅行也推出优惠，他们可以免费在最多kk种航线上搭乘飞机。那么Alice和Bob这次出行最少花费多少？
输入输出格式
输入格式：
数据的第一行有三个整数，n,m,kn,m,k，分别表示城市数，航线数和免费乘坐次数。
第二行有两个整数，s,ts,t，分别表示他们出行的起点城市编号和终点城市编号。
接下来有m行，每行三个整数，a,b,ca,b,c，表示存在一种航线，能从城市aa到达城市bb，或从城市bb到达城市aa，价格为cc。
输出格式：
只有一行，包含一个整数，为最少花费。
输入输出样例
说明
对于30%的数据,2 le n le 50,1 le m le 300,k=02≤n≤50,1≤m≤300,k=0;
对于50%的数据,2 le n le 600,1 le m le 6000,0 le k le 12≤n≤600,1≤m≤6000,0≤k≤1;
对于100%的数据,2 le n le 10000,1 le m le 50000,0 le k le 102≤n≤10000,1≤m≤50000,0≤k≤10,0 le s,t<n,0 le a,b<n,a
eq b,0 le c le 10000≤s,t<n,0≤a,b<n,a≠b,0≤c≤1000
题解
把原图建k+1层，其中第i层表示用掉了(i-1)次免费票的旅程。
对于每条边，再在相邻一层的方向建免费边。（原图：$u→v$；免费边：$u_{第i层}→v_{第(i+1)层}$）
然后从第一层的$s$跑到第(k+1)层的$t$就好了。
感觉这个图建的非常有网络流的感觉呢。
1 qwerta 2 P4568 [JLOI2011]飞行路线 Accepted 3 100 4 代码 C++，1.24KB 5 提交时间 2018-11-02 19:35:30 6 耗时/内存 617ms, 26264KB 7 #include<iostream> 8 #include<cstring> 9 #include<cstdio> 10 #include<queue> 11 using namespace std; 12 const int MAXN=10000+3,MAXM=50000+3; 13 struct emm{ 14 int e,f,l; 15 }a[11*4*MAXM]; 16 int h[11*MAXN]; 17 int tot=0; 18 int n,k; 19 void con(int x,int y,int l) 20 { 21 //cout<<"con "<<x<<" "<<y<<" "<<l<<endl; 22 a[++tot].f=h[x]; 23 h[x]=tot; 24 a[tot].e=y; 25 a[tot].l=l; 26 return; 27 } 28 void add(int x,int y,int l) 29 { 30 for(int c=0;c<=k;++c) 31 { 32 int u=x+c*n,v=y+c*n; 33 con(u,v,l); 34 con(v,u,l); 35 } 36 for(int c=0;c<k;++c) 37 { 38 int u=x+c*n,v=y+(c+1)*n; 39 con(u,v,0); 40 u=x+(c+1)*n,v=y+c*n; 41 con(v,u,0); 42 } 43 } 44 struct ahh{ 45 int nod,v; 46 }; 47 struct cmp{ 48 bool operator()(ahh qaq,ahh qwq){ 49 return qaq.v>qwq.v; 50 }; 51 }; 52 priority_queue<ahh,vector<ahh>,cmp>q; 53 int d[11*MAXN]; 54 bool sf[11*MAXN]; 55 int main() 56 { 57 //freopen("a.in","r",stdin); 58 int m; 59 scanf("%d%d%d",&n,&m,&k); 60 int s,t; 61 scanf("%d%d",&s,&t); 62 for(int i=1;i<=m;++i) 63 { 64 int x,y,l; 65 scanf("%d%d%d",&x,&y,&l); 66 add(x,y,l); 67 } 68 t=k*n+t; 69 //cout<<s<<" "<<t<<endl; 70 memset(d,127,sizeof(d)); 71 d[s]=0; 72 q.push((ahh){s,0}); 73 while(!q.empty()) 74 { 75 int x; 76 do{x=q.top().nod;q.pop();}while(sf[x]&&!q.empty()); 77 sf[x]=1; 78 for(int i=h[x];i;i=a[i].f) 79 if(d[a[i].e]>d[x]+a[i].l) 80 { 81 d[a[i].e]=d[x]+a[i].l; 82 q.push((ahh){a[i].e,d[a[i].e]}); 83 } 84 } 85 cout<<d[t]; 86 return 0; 87 }