洛谷P4568 [JLOI2011] 飞行路线 题解

题目链接：P4568 [JLOI2011] 飞行路线

题意：

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

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

对于 \(100\%\) 的数据，\(2 \le n \le 10^4\)，\(1 \le m \le 5\times 10^4\)，\(0 \le k \le 10\)，\(0\le s,t,a,b\le n\)，\(a\ne b\)，\(0\le c\le 10^3\)。

分层图板子题

不写具体做法了，就总结几个易错点

• 无向图的e数组开 \[ M\times (K+1) \times 4 \] \(M\) 稍微大一点（比如5e4+5）用于后面的额外边

• 额外边：如果 \(s\to t\) 的路径，结点数小于 \(k\)

  则需要单独建边

  for(int i=1; i<=k; i++)
      addEdge((i-1)*n+t,i*n+t,0);

  这样答案才是 d[k*n+t]

时间复杂度 \(O(nk\log mk)\)

代码：

#include <iostream>
#include <string>
#include <vector>
#include <algorithm>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <cmath>
#include <iomanip>
#include <queue>
using namespace std;
#define int long long
#define INF 0x3f3f3f3f3f3f3f3f
#define N (int)(1e4+5)
#define M (int)(5e4+5)
#define K (int)(11)
struct Edge
{
    int u,v,w,next;
}e[M*(K+1)*4];
int n,m,k,s,t,pos=1,head[N*(K+1)],d[N*(K+1)],vis[N*(K+1)];
struct node{int u,dis;};
bool operator<(node a,node b){return a.dis>b.dis;}
priority_queue<node> q;
void addEdge(int u,int v,int w)
{
    e[++pos]={u,v,w,head[u]};
    head[u]=pos;
}
void dijkstra(int st)
{
    memset(d,0x3f,sizeof(d));
    q.push({st,0}); d[st]=0;
    while(!q.empty())
    {
        int u=q.top().u; q.pop();
        if(vis[u])continue;
        vis[u]=1;
        for(int i=head[u]; i; i=e[i].next)
        {
            int v=e[i].v,w=e[i].w;
            if(d[v]>d[u]+w)
            {
                d[v]=d[u]+w;
                q.push({v,d[v]});
            }
        }
    }

}
signed main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);cout.tie(0);
    // freopen("check.in","r",stdin);
    // freopen("check.out","w",stdout);
    cin >> n >> m >> k >> s >> t; ++s; ++t;
    for(int i=1,u,v,w; i<=m; i++)
    {
        cin >> u >> v >> w; ++u; ++v;
        addEdge(u,v,w);addEdge(v,u,w);
        for(int j=1; j<=k; j++)
        {
            addEdge(j*n+u,j*n+v,w);
            addEdge(j*n+v,j*n+u,w);
            addEdge((j-1)*n+u,j*n+v,0);
            addEdge((j-1)*n+v,j*n+u,0);
        }
    }
    for(int i=1; i<=k; i++)
        addEdge((i-1)*n+t,i*n+t,0);
    dijkstra(s);
    cout << d[k*n+t] << '\n';
    return 0;
}