企业官网建设流程全解析

P4568 [JLOI2011] 飞行路线

题目描述

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

Alice and Bob now need to travel from one city to another along the routes, with possible transfers in between. The airline is also offering a special deal for this trip: they can fly for free on up tok kkroutes. So what is the minimum cost for Alice and Bob’s trip?

输入格式

第一行三个整数n , m , k n,m,kn,m,k，分别表示城市数，航线数和免费乘坐次数。

接下来一行两个整数s , t s,ts,t，分别表示他们出行的起点城市编号和终点城市编号。

接下来m mm行，每行三个整数a , b , c a,b,ca,b,c，表示存在一种航线，能从城市a aa到达城市b bb，或从城市b bb到达城市a aa，价格为c cc。

输出格式

输出一行一个整数，为最少花费。

输入输出样例 #1

输入 #1

5 6 1 0 4 0 1 5 1 2 5 2 3 5 3 4 5 2 3 3 0 2 100

输出 #1

8

说明/提示

数据规模与约定

对于30 % 30\%30%的数据，2 ≤ n ≤ 50 2 \le n \le 502≤n≤50，1 ≤ m ≤ 300 1 \le m \le 3001≤m≤300，k = 0 k=0k=0。

对于50 % 50\%50%的数据，2 ≤ n ≤ 600 2 \le n \le 6002≤n≤600，1 ≤ m ≤ 6 × 10 3 1 \le m \le 6\times10^31≤m≤6×103，0 ≤ k ≤ 1 0 \le k \le 10≤k≤1。

对于100 % 100\%100%的数据，2 ≤ n ≤ 10 4 2 \le n \le 10^42≤n≤104，1 ≤ m ≤ 5 × 10 4 1 \le m \le 5\times 10^41≤m≤5×104，0 ≤ k ≤ 10 0 \le k \le 100≤k≤10，0 ≤ s , t , a , b < n 0\le s,t,a,b < n0≤s,t,a,b<n，a ≠ b a\ne ba=b，0 ≤ c ≤ 10 3 0\le c\le 10^30≤c≤103。

另外存在一组 hack 数据。

题解

建图模型：

我们将每个城市u uu拆分成k + 1 k+1k+1个节点，记为( u , j ) (u, j)(u,j)，其中0 ≤ j ≤ k 0 \le j \le k0≤j≤k。
( u , j ) (u, j)(u,j)表示当前位于城市u uu，且已经使用了j jj次免费机会的状态。

边的构建：

对于原图中的一条边( a , b , c ) (a, b, c)(a,b,c)：

• 付费乘坐：从( a , j ) (a, j)(a,j)到( b , j ) (b, j)(b,j)连一条权值为c cc的边；从( b , j ) (b, j)(b,j)到( a , j ) (a, j)(a,j)连一条权值为c cc的边。（不消耗免费次数）
• 免费乘坐：如果j < k j < kj<k，从( a , j ) (a, j)(a,j)到( b , j + 1 ) (b, j+1)(b,j+1)连一条权值为0 00的边；从( b , j ) (b, j)(b,j)到( a , j + 1 ) (a, j+1)(a,j+1)连一条权值为0 00的边。（消耗一次免费次数）

运行 Dijkstra：

以( s , 0 ) (s, 0)(s,0)为源点跑 Dijkstra 算法。
最终答案为min ⁡ { d i s t [ t ] [ j ] ∣ 0 ≤ j ≤ k } \min\{dist[t][j] \mid 0 \le j \le k\}min{dist[t][j]∣0≤j≤k}，即到达终点t tt时使用了任意不超过k kk次免费机会的最小花费。

复杂度分析：

• 节点数：n × ( k + 1 ) ≤ 10 4 × 11 = 1.1 × 10 5 n \times (k+1) \le 10^4 \times 11 = 1.1 \times 10^5n×(k+1)≤104×11=1.1×105
• 边数：每条原边产生O ( k ) O(k)O(k)条新边，总边数约m × k × 2 ≈ 5 × 10 4 × 10 × 2 = 10 6 m \times k \times 2 \approx 5 \times 10^4 \times 10 \times 2 = 10^6m×k×2≈5×104×10×2=106
• Dijkstra 使用优先队列，时间复杂度O ( E log ⁡ V ) O(E \log V)O(ElogV)，完全可以通过。

代码

#include<iostream>#include<cstring>#include<algorithm>#include<vector>#include<queue>usingnamespacestd;typedeflonglongLL;typedefpair<LL,int>PLI;constLL INF=1e18;constintN=1e4+10,K=11;structedge{intne;LL w;};intn,m,k;ints,t;vector<vector<edge>>adj(N*K);LL dist[N*K];boolst[N*K];intmain(){ios::sync_with_stdio(false);cin.tie(0);cin>>n>>m>>k>>s>>t;intlayers=k+1;for(inti=0;i<m;i++){inta,b,c;cin>>a>>b>>c;for(intj=0;j<=k;j++){// 付费边adj[a*layers+j].push_back({b*layers+j,c});adj[b*layers+j].push_back({a*layers+j,c});// 免费边if(j<k){adj[a*layers+j].push_back({b*layers+j+1,0});adj[b*layers+j].push_back({a*layers+j+1,0});}}}// Dijkstrafor(inti=0;i<N*K;i++)dist[i]=INF;priority_queue<PLI,vector<PLI>,greater<>>q;dist[s*layers+0]=0;q.push({0,s*layers+0});while(q.size()){auto[d,u]=q.top();q.pop();if(st[u])continue;st[u]=true;for(auto&e:adj[u]){LL nd=d+e.w;if(nd<dist[e.ne]){dist[e.ne]=nd;q.push({nd,e.ne});}}}LL res=INF;for(intj=0;j<=k;j++)res=min(res,dist[t*layers+j]);cout<<res<<endl;return0;}