題目描述

Alice和Bob現(xiàn)在要乘飛機(jī)旅行，他們選擇了一家相對便宜的航空公司。該航空公司一共在nn個(gè)城市設(shè)有業(yè)務(wù)，設(shè)這些城市分別標(biāo)記為00到n-1n?1，一共有mm種航線，每種航線連接兩個(gè)城市，并且航線有一定的價(jià)格。

Alice和Bob現(xiàn)在要從一個(gè)城市沿著航線到達(dá)另一個(gè)城市，途中可以進(jìn)行轉(zhuǎn)機(jī)。航空公司對他們這次旅行也推出優(yōu)惠，他們可以免費(fèi)在最多kk種航線上搭乘飛機(jī)。那么Alice和Bob這次出行最少花費(fèi)多少？

輸入格式

數(shù)據(jù)的第一行有三個(gè)整數(shù)，n,m,kn,m,k，分別表示城市數(shù)，航線數(shù)和免費(fèi)乘坐次數(shù)。
第二行有兩個(gè)整數(shù)，s,ts,t，分別表示他們出行的起點(diǎn)城市編號和終點(diǎn)城市編號。
接下來有m行，每行三個(gè)整數(shù)，a,b,ca,b,c，表示存在一種航線，能從城市aa到達(dá)城市bb，或從城市bb到達(dá)城市aa，價(jià)格為cc。

輸出格式

只有一行，包含一個(gè)整數(shù)，為最少花費(fèi)

輸入 #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

【解題思路】

分層圖模板題

我們將每個(gè)點(diǎn)拆成k個(gè)，這樣子在路徑上就能夠表現(xiàn)出，選擇簡化這個(gè)點(diǎn)到另外一個(gè)點(diǎn)的路徑對結(jié)果的影響

因?yàn)閯偤檬莐層，所以能夠優(yōu)化的路徑也就至多只有k層，保證了選擇k條路徑的前提

有點(diǎn) u ，v ，令第 j - 1 層的 u 到第 j 層的 v 連邊，代價(jià)為 0 ，這樣子就能夠表示這條路徑被優(yōu)化，同時(shí)又消耗了一次免費(fèi)機(jī)會

注意：因?yàn)槭请p向邊，所以同時(shí)也要連一條反向邊

第 j 層的 u ，v 同時(shí)也要連一條邊，代價(jià)為 c ，令優(yōu)化過的 u 能夠在不優(yōu)化的情況下到達(dá) v

得到這個(gè)新的圖之后，我們在上面跑一遍最短路，就能夠得到正確結(jié)果

因?yàn)樽疃搪芬呀?jīng)利用所有的 k 次機(jī)會優(yōu)化了整個(gè)過程

?

【代碼】

?

#include<cstdio> #include<iostream> #include<algorithm> #include<queue> #include<cstring> #define ll long long using namespace std; typedef pair<int, int> P; const int MAXN = 110010; const int MAXM = 4100010; const ll INF = (1ll << 62) - 1; struct note {int to;int nt;ll cost; }; struct edge {note arr[MAXM];int st[MAXN];ll dis[MAXN];int top;int n, m, s, t,k;edge(){memset(st, -1, sizeof(st));memset(dis, -1, sizeof(dis));top = 0;}void read(){top = 0;scanf("%d%d%d", &n, &m, &k);scanf("%d%d", &s, &t);s++, t++;for (int i = 1; i <= m; i++){int u, v;ll c;scanf("%d%d%lld", &u, &v, &c);u++, v++;add(u, v, c);add(v, u, c);for (int j = 1; j <= k; j++){add(u+( j - 1 )*n, v + j*n, 0);add(v+( j - 1 )*n, u + j*n, 0);add(u + j * n, v + j * n, c);add(v + j * n, u + j * n, c);}}for (int i = 1; i <= k; ++i){add(t + (i - 1)*n, t + i * n,0);}t += k * n;n = n * (k+1)+1;}void add(int x, int y, ll c){top++; arr[top] = { y,st[x],c }; st[x] = top;}ll min_dis(){priority_queue<P,vector<P>,greater<P> > q;fill(dis+1, dis + n+1, INF);dis[s] = 0;q.push(P(0, s));while (!q.empty()){P p = q.top();q.pop();int v = p.second;if (dis[v] < p.first) continue;for (int i = st[v]; i != -1; i = arr[i].nt){int to = arr[i].to;if (dis[to] > dis[v] + arr[i].cost){dis[to] = dis[v] + arr[i].cost;q.push(P(dis[to], to));}}}return dis[t];} }; edge road; int main() {road.read();printf("%lld", road.min_dis());return 0; } View Code

?

轉(zhuǎn)載于:https://www.cnblogs.com/rentu/p/11320650.html

總結(jié)

以上是生活随笔為你收集整理的【JLOI2011】飞行路线的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。