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输入 #15 6 1 0 4 0 1 5 1 2 5 2 3 5 3 4 5 2 3 3 0 2 100输出 #18说明/提示数据规模与约定对于30 % 30\%30%的数据2 ≤ n ≤ 50 2 \le n \le 502≤n≤501 ≤ m ≤ 300 1 \le m \le 3001≤m≤300k 0 k0k0。对于50 % 50\%50%的数据2 ≤ n ≤ 600 2 \le n \le 6002≤n≤6001 ≤ m ≤ 6 × 10 3 1 \le m \le 6\times10^31≤m≤6×1030 ≤ k ≤ 1 0 \le k \le 10≤k≤1。对于100 % 100\%100%的数据2 ≤ n ≤ 10 4 2 \le n \le 10^42≤n≤1041 ≤ m ≤ 5 × 10 4 1 \le m \le 5\times 10^41≤m≤5×1040 ≤ k ≤ 10 0 \le k \le 100≤k≤100 ≤ s , t , a , b n 0\le s,t,a,b n0≤s,t,a,bna ≠ b a\ne bab0 ≤ c ≤ 10 3 0\le c\le 10^30≤c≤103。另外存在一组 hack 数据。题解建图模型我们将每个城市u uu拆分成k 1 k1k1个节点记为( 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 kjk从( a , j ) (a, j)(a,j)到( b , j 1 ) (b, j1)(b,j1)连一条权值为0 00的边从( b , j ) (b, j)(b,j)到( a , j 1 ) (a, j1)(a,j1)连一条权值为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 (k1) \le 10^4 \times 11 1.1 \times 10^5n×(k1)≤104×111.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×2106Dijkstra 使用优先队列时间复杂度O ( E log ⁡ V ) O(E \log V)O(ElogV)完全可以通过。代码#includeiostream#includecstring#includealgorithm#includevector#includequeueusingnamespacestd;typedeflonglongLL;typedefpairLL,intPLI;constLL INF1e18;constintN1e410,K11;structedge{intne;LL w;};intn,m,k;ints,t;vectorvectoredgeadj(N*K);LL dist[N*K];boolst[N*K];intmain(){ios::sync_with_stdio(false);cin.tie(0);cinnmkst;intlayersk1;for(inti0;im;i){inta,b,c;cinabc;for(intj0;jk;j){// 付费边adj[a*layersj].push_back({b*layersj,c});adj[b*layersj].push_back({a*layersj,c});// 免费边if(jk){adj[a*layersj].push_back({b*layersj1,0});adj[b*layersj].push_back({a*layersj1,0});}}}// Dijkstrafor(inti0;iN*K;i)dist[i]INF;priority_queuePLI,vectorPLI,greaterq;dist[s*layers0]0;q.push({0,s*layers0});while(q.size()){auto[d,u]q.top();q.pop();if(st[u])continue;st[u]true;for(autoe:adj[u]){LL ndde.w;if(nddist[e.ne]){dist[e.ne]nd;q.push({nd,e.ne});}}}LL resINF;for(intj0;jk;j)resmin(res,dist[t*layersj]);coutresendl;return0;}