【习题·图论】[JLOI2011]飞行路线：拆点最短路

题目描述

Alice和Bob现在要乘飞机旅行，他们选择了一家相对便宜的航空公司。该航空公司一共在n个城市设有业务，设这些城市分别标记为0到n?1，一共有m种航线，每种航线连接两个城市，并且航线有一定的价格。

Alice和Bob现在要从一个城市沿着航线到达另一个城市，途中可以进行转机。航空公司对他们这次旅行也推出优惠，他们可以免费在最多k种航线上搭乘飞机。那么Alice和Bob这次出行最少花费多少？

Solution

可以知道，这道题目一定是最短路；但是多了一个限制：有$k$条路线可以免费。

此时，若以点为单位跑最短路显然不行。我们需要拆点，或者说是分层图：

其中$d(u,fre)$表示到节点$u$，使用了$fre$次免费搭乘的最小话费。

就是这样的（盗个图）：

那么如何在最短路里进行点与点之间的转移呢？

可以得到：$$d(u,fre)+val\to d(v,fre),不用免费换乘$$
$$d(u,fre)\to d(v,fre+1),使用免费换乘.$$

其中$u$和$v$相连，边权为$val$。那么最后的答案$ans=d(e,i),i\in [0,k].$

代码如下：

#include<bits/stdc++.h>
using namespace std;
#define Mp make_pair
struct edge{
    int pnt,val;
};
int n,m,k,S,T;
int d[20000][20];
int v[20000][20];
vector<edge>a[20000];
inline int read()
{
    int s=0;char c=getchar();while (c<'0' || c>'9') c=getchar();while (c>='0' && c<='9') s=s*10+c-48,c=getchar();return s;
} 
int main(void)
{
    int n=read(),m=read(),k=read();int S=read()+1,T=read()+1;for (int i=1;i<=m;++i){
    int x=read()+1,y=read()+1,v=read();a[x].push_back(edge{
    y,v});a[y].push_back(edge{
    x,v});}memset(d,30,sizeof(d));d[S][0]=0;priority_queue< pair<int,pair<int,int> > > q;q.push(Mp(0,Mp(S,0)));while (q.size()){
    int now=q.top().second.first;int fre=q.top().second.second;q.pop();if (v[now][fre]) continue;else v[now][fre]=1;for (int i=0;i<a[now].size();++i){
    int Next=a[now][i].pnt;int Val=a[now][i].val;if (d[now][fre]+Val<d[Next][fre]){
    d[Next][fre]=d[now][fre]+Val;q.push(Mp(-d[Next][fre],Mp(Next,fre)));}if (d[now][fre]<d[Next][fre+1] && fre<k){
    d[Next][fre+1]=d[now][fre];q.push(make_pair(-d[Next][fre+1],Mp(Next,fre+1)));}}}int ans=INT_MAX;for (int i=0;i<=k;++i) ans=min(ans,d[T][i]);printf("%d\n",ans);return 0;
}