优惠通行

思路与复杂度

状态为城市和已经使用的优惠券张数；每条边提供原价转移，尚有券时提供 floor(w/2) 转移到下一层。边权非负，使用Dijkstra，答案取终点所有层距离的最小值。时间 O((n+m)(k+1) log(n(k+1)))，空间 O(n(k+1)+m)。

正确性与边界

层数准确表示已经使用的券，枚举用券或不用券覆盖所有可行选择。

参考代码

#include<bits/stdc++.h>
using namespace std;using ll=long long;const ll I=(1LL<<62);struct E{int v;ll w;};int main(){ios::sync_with_stdio(0);cin.tie(0);int n,m,k;cin>>n>>m>>k;vector<vector<E>>g(n+1);while(m--){int u,v;ll w;cin>>u>>v>>w;g[u].push_back({v,w});g[v].push_back({u,w});}vector<vector<ll>>d(n+1,vector<ll>(k+1,I));using T=tuple<ll,int,int>;priority_queue<T,vector<T>,greater<T>>q;d[1][0]=0;q.push({0,1,0});while(q.size()){auto[du,u,c]=q.top();q.pop();if(du!=d[u][c])continue;for(auto e:g[u]){if(d[e.v][c]>du+e.w)d[e.v][c]=du+e.w,q.push({d[e.v][c],e.v,c});if(c<k&&d[e.v][c+1]>du+e.w/2)d[e.v][c+1]=du+e.w/2,q.push({d[e.v][c+1],e.v,c+1});}}cout<<*min_element(d[n].begin(),d[n].end())<<"\n";}