[JLOI2011]飞行路线（dijkstra分层最短路）

题目链接：K-[JLOI2011]飞行路线_WUT2021校内训练⑦ (nowcoder.com)

题意请看原题，是中文的。

思路

本题突破口在K <= 10，且N <= 1e4。

设起点s, 终点t。

一般的最短路的题目都是建立一个二维图，这里我们建立一个K层的三维图，从第 0 层开始，第 i 层表示用了 i 次免费航线。这样最后统计所有t + N * i(0 <= i <= K)的点到源点的距离的最小值即可。

建图使用了一维拓展的方式，[0, N - 1]表示第一层，[N, 2 * N - 1]表示第二层，以此类推。

需要注意的是，建图的时候，需要给每一层的二维图都建立起边，并且将相邻的两层之间建立权值为0的免费航线。具体实现方法看代码。

代码

/*Copyright (C) Eriktse 2022*/
#include <iostream>
#include <cstdio>
#include <stack>
#include <queue>
#include <cmath>
#include <cstring>
#include <string>
#include <vector>
#include <map>
#include <bitset>
#include <utility>
#define fi first
#define se second
#define gc getchar
#define pr printf
#define pb push_back
#define sc scanf
#define int long long
//用%lld输出long long类型数据
using namespace std;
inline int readInt()
{
     int s = 0,w = 1;char c = gc();
     while(c < '0' || c > '9'){if(c == '-')w = -1;c = gc();}
     while('0' <= c && c <= '9'){s = s * 10 + c - '0',c = gc();}
     return s * w;
}
/*--------全局变量--------*/
const int maxn = 1e5 + 2e4 + 10,inf = 1e15;
int N, M, K, s, t;

struct Node
{
     int x, d;
     bool operator < (const Node &m)const{return d > m.d;}
};
vector<Node> g[maxn];
int dist[maxn];
/*--------自定义函数-------*/

inline bool dijkstra(int s,int t)
{
     memset(dist, 127, sizeof dist);
     priority_queue<Node> pq;
     pq.push({s, 0});
     while(!pq.empty())
     {
          int x = pq.top().x;
          int d = pq.top().d;
          pq.pop();
          if(x == t)return 1;
          if(d > dist[x])continue;
          for(auto i : g[x])
               if(d + i.d < dist[i.x])pq.push({i.x, dist[i.x] = d + i.d});
     }
     return 0;
}

signed main()
{
     N = readInt(), M = readInt(), K = readInt();
     s = readInt(), t = readInt();
     while(M --)
     {
          int x = readInt(), y = readInt(), w = readInt();
          for(int i = 0;i <= K; ++ i)
          {
               g[x + N * i].pb({y + N * (i + 1), 0});
               g[y + N * i].pb({x + N * (i + 1), 0});
               g[x + N * i].pb({y + N * i, w});
               g[y + N * i].pb({x + N * i, w});
          }
     }
     dijkstra(s, t);
     int ans = inf;
     for(int i = 0;i <= K; ++ i)ans = min(ans, dist[t + N * i]);
     pr("%lld\n",ans);
     return 0;
}