[JLOI2011]飞行路线

Link: https://www.luogu.com.cn/problem/P4568

Description

点击查看题面

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

输入描述:

数据的第一行有三个整数，n,m,k，分别表示城市数，航线数和免费乘坐次数。
第二行有两个整数，s,t，分别表示他们出行的起点城市编号和终点城市编号。(0 ≤ s,t < n)
接下来有m行，每行三个整数，a,b,c，表示存在一种航线，能从城市a到达城市b，或从城市b到达城市a，价格为c。(0 ≤ a,b < n,a与b不相等，0 ≤ c ≤ 1000)

输出描述:

只有一行，包含一个整数，为最少花费。
示例1
输入
5 6 1
0 4
0 1 5
1 2 5
2 3 5
3 4 5
2 3 3
0 2 100
输出
8

数据范围

Problem solving

这道题的意思就是给你一个图，你有次机会可以让你走的路零代价，给你起点和终点，问你最短距离。
~一开始想着贪心着写，贪着贪着发现，我还是不够贪心~

后来才知道这就是一道模板题——分层图最短路。
网上讲解挺多的，大致意思就是有两种方法。一种是dp，一种是建图的时候直接建分层图。但是后者容易被卡空间。
不过在这里显然不用担心。

具体思路，就是，建图的时候，建层。每层图根原图是一样的。但是在每一层之间，如果这两个点是联通的就加上一条权值为0的边。然后我们跑一边最短路。答案就是从起点到每一层的终点对应的点的最短路的最小值。
这思路挺妙的，如果你某次使某条路代价为零就等价于，从这几层图的中间选择了一条路。

还有就是这种分法很占空间。我开了才过。

Code

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
#define pb push_back
#define mp make_pair
const int maxn = 3e6+10;
const int mod = 1e9+7;
const int INF = 0x3f3f3f3f;
int n,m,k,s,t,head[maxn],cnt=1,dis[maxn];
struct node{
    int to,next,val;
}p[maxn];
void add(int u,int v,int w){
    p[cnt].to=v;
    p[cnt].next=head[u];
    p[cnt].val=w;
    head[u]=cnt++;
}
void solve(int s){
    memset(dis,INF,sizeof(dis));
    dis[s]=0;
    priority_queue<pair<int,int> > q;
    q.push(mp(0,s));
    while(!q.empty()){
        int u=q.top().second;q.pop();
        for(int i=head[u];i;i=p[i].next){
            int v=p[i].to;
            if(dis[v]>dis[u]+p[i].val){
                dis[v]=dis[u]+p[i].val;
                q.push(mp(-dis[v],v));
            }
        }
    }
}
int main() {
    ios::sync_with_stdio(0);
    #ifdef Uncle_drew
    freopen("in.txt","r",stdin);
    freopen("out.txt","w",stdout);
    #else
    #endif
    cin>>n>>m>>k>>s>>t;
    for(int i=0,u,v,w;i<m;i++){
        cin>>u>>v>>w;
        for(int j=0;j<=k;j++){
            add(u+j*n,v+j*n,w);
            add(v+j*n,u+j*n,w);
            if(j<k){
                add(u+j*n,v+(j+1)*n,0);
                add(v+j*n,u+(j+1)*n,0);
            }
        }
    }//建图
    solve(s);
    int ans=INF;
    for(int i=0;i<=k;i++){
        // cout<<dis[i*n+t]<<endl;
        ans=min(ans,dis[i*n+t]);
    }
    cout<<ans<<endl;
    return 0;
}
赏