題目描述

? “我要成為魔法少女！”???
? “那么，以靈魂為代價(jià)，你希望得到什么？”?
“我要將有關(guān)魔法和奇跡的一切，封印于卡片之中??”???
? 在這個(gè)愿望被實(shí)現(xiàn)以后的世界里，人們享受著魔法卡片（SpellCard，又名符
卡）帶來的便捷。?
現(xiàn)在，不需要立下契約也可以使用魔法了！你還不來試一試？?
? 比如，我們在魔法百科全書（Encyclopedia? of? Spells）里用“freeze”作為關(guān)
鍵字來查詢，會有很多有趣的結(jié)果。?
例如，我們熟知的Cirno，她的冰凍魔法當(dāng)然會有對應(yīng)的 SpellCard 了。 當(dāng)然，
更加令人驚訝的是，居然有凍結(jié)時(shí)間的魔法，Cirno 的凍青蛙比起這些來真是小
巫見大巫了。?
這說明之前的世界中有很多魔法少女曾許下控制時(shí)間的愿望，比如 Akemi?
Homura、Sakuya Izayoi、???
當(dāng)然，在本題中我們并不是要來研究歷史的，而是研究魔法的應(yīng)用。?
我們考慮最簡單的旅行問題吧：? 現(xiàn)在這個(gè)大陸上有 N 個(gè)城市，M 條雙向的
道路。城市編號為 1~N，我們在 1 號城市，需要到 N 號城市，怎樣才能最快地
到達(dá)呢？?
? 這不就是最短路問題嗎？我們都知道可以用 Dijkstra、Bellman-Ford、
Floyd-Warshall等算法來解決。?
? 現(xiàn)在，我們一共有 K 張可以使時(shí)間變慢 50%的 SpellCard，也就是說，在通
過某條路徑時(shí)，我們可以選擇使用一張卡片，這樣，我們通過這一條道路的時(shí)間
就可以減少到原先的一半。需要注意的是：?
? 1. 在一條道路上最多只能使用一張 SpellCard。?
? 2. 使用一張SpellCard 只在一條道路上起作用。?
? 3. 你不必使用完所有的 SpellCard。?
? 給定以上的信息，你的任務(wù)是：求出在可以使用這不超過 K 張時(shí)間減速的
SpellCard 之情形下，從城市1 到城市N最少需要多長時(shí)間。

輸入

第一行包含三個(gè)整數(shù)：N、M、K。?
接下來 M 行，每行包含三個(gè)整數(shù)：Ai、Bi、Timei，表示存在一條 Ai與 Bi之
間的雙向道路，在不使用 SpellCard 之前提下，通過它需要 Timei的時(shí)間。

輸出

輸出一個(gè)整數(shù)，表示從1 號城市到 N號城市的最小用時(shí)。?

樣例輸入

4 4 1
1 2 4
4 2 6
1 3 8
3 4 8

樣例輸出

7
【樣例1 解釋】
在不使用 SpellCard 時(shí)，最短路為 1à2à4，總時(shí)間為 10。現(xiàn)在我們可
以使用 1 次 SpellCard，那么我們將通過 2à4 這條道路的時(shí)間減半，此時(shí)總
時(shí)間為7。

提示

對于100%的數(shù)據(jù)：1? ≤? K? ≤? N ≤? 50，M? ≤? 1000。?

? 1≤? Ai，Bi ≤? N，2 ≤? Timei? ≤? 2000。?

為保證答案為整數(shù)，保證所有的 Timei均為偶數(shù)。?

所有數(shù)據(jù)中的無向圖保證無自環(huán)、重邊，且是連通的。

?

　　分層圖最短路，建立k+1層圖，對于每條雙向邊a,b,c，a連向b邊權(quán)為c，b連向a邊權(quán)為c，a連向下一層的b邊權(quán)為c/2，b連向下一層的a邊權(quán)為c/2，最后找出每層中n的最短路的最小值。

#include<cstdio> #include<algorithm> #include<iostream> #include<cstring> #include<cmath> #include<map> #include<queue> #include<vector> using namespace std; typedef pair<int,int> pr; int n,m,k; int head[2000010]; int next[2000010]; int val[2000010]; int to[2000010]; int d[2000010]; int vis[2000010]; int tot; int a,b,c; int ans; void add(int x,int y,int z) {tot++;next[tot]=head[x];head[x]=tot;to[tot]=y;val[tot]=z; } priority_queue<pr,vector<pr>,greater<pr> >q; void dijkstar() {memset(d,0x3f,sizeof(d));d[1]=0;q.push(make_pair(0,1));while(!q.empty()){int now=q.top().second;q.pop();if(vis[now]){continue;}vis[now]=1;for(int i=head[now];i;i=next[i]){if(d[to[i]]>d[now]+val[i]){d[to[i]]=d[now]+val[i];q.push(make_pair(d[to[i]],to[i]));}}}ans=2147483647;for(int i=0;i<=k+1;i++){ans=min(ans,d[n*i]);}printf("%d",ans); } int main() {scanf("%d%d%d",&n,&m,&k);for(int i=1;i<=m;i++){scanf("%d%d%d",&a,&b,&c);for(int j=0;j<=k;j++){add(a+n*j,b+n*j,c);add(b+n*j,a+n*j,c);add(a+n*j,b+n*(j+1),c/2);add(b+n*j,a+n*(j+1),c/2);}}dijkstar(); }

轉(zhuǎn)載于:https://www.cnblogs.com/Khada-Jhin/p/9301850.html

總結(jié)

以上是生活随笔為你收集整理的BZOJ2662[BeiJing wc2012]冻结——分层图最短路的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

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