算法思路

本题是 分层图最短路 的经典应用，典中典，没有更典了。

我们考虑将"使用滑翔技能的次数"作为分层依据，构建 \(k+1\) 层图。每层对应使用了 \(j\) 次滑翔技能的状态（\(0 \le j \le k\)）。

1. 分层图构建：

   • 每层有 \(n\) 个节点，节点编号为 i + j * n，其中 \(i\) 是原图节点编号，\(j\) 是使用滑翔技能的次数
   • 对于原图每条双向边 \((u, v)\)，在每层 \(j\) 中添加两条边：
     • 普通飞行：u + j*n ↔ v + j*n，边权为 \(|h_u - h_v|\)
     • 滑翔飞行（仅当 \(j < k\) 时）：u + j*n ↔ v + (j+1)*n，边权为 \(\lfloor|h_u - h_v|/2\rfloor\)

2. 最短路计算：

   • 起点为 1 + 0*n = 1（第0层的1号节点）
   • 终点为所有层的 \(n\) 号节点（n + j*n，\(0 \le j \le k\)）中的最小值
   • 使用Dijkstra算法在分层图上求解最短路

时间复杂度

• 节点总数：\(n \times (k+1) \le 10^4 \times 21 = 2.1 \times 10^5\)
• 边总数：\(m \times 2 \times (k+1) \le 2 \times 10^4 \times 2 \times 21 = 8.4 \times 10^5\)
• 时间复杂度：\(O((n(k+1) + m(k+1)) \log(n(k+1))) \approx 10^6 \log 10^5\)。

AC代码

//flpar
#include<bits/stdc++.h>
using namespace std;
#define int long long
#define rg register
#define PII pair<int,int>
const int N=1e4+5;
const int lgN=N*21; // 最多21层
const int INF=1e18;
vector<PII> g[lgN];
int h[N], dis[lgN];
int n,m,k;
void init();
signed main(){
    ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
//  init();
    cin>>n>>m>>k;
    for(int i=1;i<=n;i++)
        cin>>h[i];
    // 构建分层图
    for(int i=1;i<=m;i++){
        int u,v; cin>>u>>v;
        int w=abs(h[u]-h[v]);
        int w2=w/2;
        for(int j=0;j<=k;j++){
            // 普通飞行
            g[u+j*n].push_back({v+j*n, w});
            g[v+j*n].push_back({u+j*n, w});
            // 滑翔飞行
            if(j<k){
                g[u+j*n].push_back({v+(j+1)*n, w2});
                g[v+j*n].push_back({u+(j+1)*n, w2});
            }
        }
    }
    // Dijkstra
    priority_queue<PII, vector<PII>, greater<PII>> q;
    fill(dis, dis+lgN, INF);
    dis[1]=0;
    q.push({0, 1});
    while(!q.empty()){
        auto [d, u]=q.top(); q.pop();
        if(d>dis[u]) continue;
        for(auto [v, w]:g[u]){
            if(dis[v]>d+w){
                dis[v]=d+w;
                q.push({dis[v], v});
            }
        }
    }
    // 找所有层终点的最小值
    int ans=INF;
    for(int j=0;j<=k;j++)
        ans=min(ans, dis[n+j*n]);
    cout<<(ans==INF?-1:ans)<<'\n';
    return 0;
}
void init(){
    return;
}