HDU 3499 Flight 一遍加參數的dijkstra（C++）

題目連結：這裡

題意：

給出一個 N N 個點MM條邊的有向圖 G G ，每條邊有一個權值。同時你還可以任選一條邊，把其權值減半（向下取整）。減半之後，求出一條路徑，使其權值之和最小，輸出最小權值和。

Part I 引言

第一次遇到這道題，是教練給錯我們的題。

那一天，做完了點雙連通分量練習（HDU 3749 Financial Crisis）的我和D君去找老師要題，老師就給了我們這道題。當時，我們還想了一個像模像樣的方法，便是今天要講的算法的雛形。

後來教練又重新給了一道題，于是本題也就慢慢淡出我的視野。兩個月之後，在一次模拟賽上，竟然又遇到了這題，我成了全初一（新初二）唯一一個通過本題（和AK）的人。本蒟蒻也能AK！QWQ

Part II 正片開始

Section I 思路來源

模拟賽場上，絕大部分的人做了前兩道題，放棄了這第三題，有一位同學想正反跑兩遍SPFA然後取平均枚舉（這是對的，隻是他沒打出來），兩位AC的初二學長和教練标程都是用的分層圖。上述的兩種算法是做這道題絕大部分人用的算法，第一種時間花費較大，第二種空間花費較大。下面，我來講解一下我和D君想出來的算法。

首先，應該是先想到：求出最短路徑，取其最大邊長減半。

當然很快就能推出沖突qwq。對于下面這幅圖求1~3的最短路徑：

按照剛才的算法，最短路徑為3000+6000=90003000+6000=9000即 1−2−3 1 − 2 − 3 這一條。選擇6000減半之後，權值和為 3000+6000/2=6000 3000 + 6000 / 2 = 6000 ，要大于 10000/2=5000 10000 / 2 = 5000 ，不是最優的。

看來，必須要綜合考慮路徑長和最大邊權，才能得出最優的結果。于是這時就分出了兩種算法：

1、建圖，把圖分為兩層，第一層是沒有用過折半票，第二層是用過折半票，兩層間用邊權的一半作為有向邊連接配接。

2、動态維護路徑上的最大邊權，通過反複加減維護起點到目前節點折半過後的最短路徑（即求目前子圖的最優解）。這就是我和D君的算法，可以說是基于一種DP的思想。

Section II 思路講解

我們的算法基于一個很顯而易見的事實：要折半，肯定是選擇路徑上的權值最大的那條邊。

有人會說了：“這還用說？”的确，這很顯而易見，但這是算法的基礎思想。

證明：假設現在路徑上最大權值邊的權值為 k k ，而對另外一條權值為jj的一條邊折半，總和為 sum s u m ，那麼選擇k折半，總代價為：

sum'=sum-(k+1)/2+(j+1)/2.
           

由k>j，是以（k+1）>（j+1），（k+1）/2 >=（j+1）/2（因為是向下取整是以是大于等于），sum’ <= sum。是以，選擇最大邊權折半一定更優。

可以推出第二個推論：兩條路徑長相同時，最大邊權更短的一條更優。這也不難了解，因為最大邊權更短的一條折半的更少，比如，同是長度為10000的路徑，其中一條最大邊權為9999，另一條最大邊權為1（XD~），然後兩條路徑愉快的握握手，繼續往前走，遇到一條花費為20000的邊！

9999的邊：這下糟了，我要把票給20000，但是這樣，我的花費就足足增加了5000！我死也不給票！（真香預警）

1的邊：把票給20000吧，我的花費才加1，但20000的邊能節省10000呢！

于是兩條路徑的花費變成了：10000+5000+10000=25000和10000+1+10000=20001，足足省了4999塊錢！

既然有這兩個結論，我們可以記錄目前路徑上的最大邊權如下：

struct Heap{
    int id,me;//id表示節點編号,me表示最大邊權(?)
    long long d;//d表示起點到id的路徑長(折半過後的)
    bool operator < (const Heap &a) const{
        if(a.d!=d)return d>a.d;//距離優先
        if(me!=a.me)return me>a.me;//最大邊權其次
        return id>a.id;
    }
}node;
           

留意(?)處，一些人會問：為什麼不記錄折半後的邊權呢？這樣加的時候不是更容易嗎？這個問題大家可以先想想，一會兒我會解答的。

“然後就可以像普通dijkstra一樣跑一遍得結果啦！”有些同學喊道，瞬間沖去打代碼。我們先不理他們，等會兒他們自己會回來。大家接着往下看。

Section III 重頭戲：動态維護

那麼如何維護最大邊權呢？

很多人應該都能想到：記錄之後，像那兩條懵逼的路徑一樣，把之前的加回去，把目前的也加上。但是看上去這件事因為折半向下取整而變得挺麻煩，該如何處理呢？

看到折半向下取整，即 (折半後的k)=⌊k/2⌋ ( 折 半 後 的 k ) = ⌊ k / 2 ⌋ ，又因為 k−⌊k/2⌋=⌈k/2⌉=⌊(k+1)/2⌋ k − ⌊ k / 2 ⌋ = ⌈ k / 2 ⌉ = ⌊ ( k + 1 ) / 2 ⌋ （可以自己手推一下），是以加回去的時候，加的就是（最大邊權+1）/2。

這時可以回答為什麼存折半之後的邊更麻煩了，因為你不知道原本它是 2k+1 2 k + 1 還是 2k 2 k ，你隻能看到折半之後是 k k ，并不知道應該加回去k+1k+1還是 k k <script type="math/tex" id="MathJax-Element-27">k</script>。

是以要在原本的堆優化迪傑上加上這一段：

if(w[u][i]>=Me && dis[u]+w[u][i]/+(Me+)/<dis[e[u][i]]){//Me存儲目前node的me，dis存儲距離，w存儲邊權。
    dis[e[u][i]]=dis[u]+w[u][i]/+(Me+)/;
    node.id=e[u][i];
    node.d=dis[e[u][i]];
    node.me=w[u][i];
    q.push(node);
}
           

原來的也要保留：

if(w[u][i]<Me && dis[u]+w[u][i]<dis[e[u][i]]){
    dis[e[u][i]]=dis[u]+w[u][i];
    node.id=e[u][i];
    node.d=dis[e[u][i]];
    node.me=Me;
    q.push(node);
}
           

也可以說是分類讨論了吧（托腮）。

不要問我“如何處理字元串““如何堆優化迪傑”之類的問題，本蒟蒻難以回答，假裝大家都會吧~

我是用的map，本來也試過用Trie打，結果打炸了，就隻好乖乖用STL了。

注意要開long long，題目的範圍很大的。

完整代碼如下：

#include<cstdio>
#include<map>
#include<queue>
#include<cstring>
#include<cstdlib>
#include<iostream>
#include<algorithm>
using namespace std;
vector<int> e[];//去向的節點
vector<int> w[];//邊權
struct Heap{
    int id,me;
    long long d;
    bool operator < (const Heap &a) const{
        if(a.d!=d)return d>a.d;
        if(me!=a.me)return me>a.me;
        return id>a.id;
    }
}node;
priority_queue<Heap> q;//堆
int n,m,dist,tot=,s,E,a,b;//城市數，飛機數，臨時邊權，節點編号最大值，起點終點，臨時存儲
int u,di,Me;//臨時存儲d,id,me。
string s1,s2;//字元串
long long dis[];//到起點的最短距離
map<string,int> M;//map大法好啊~

int main(){
    while(scanf("%d%d",&n,&m)!=EOF){
        M.clear(); tot=;
        for(int i=;i<=;i++){
            e[i].clear(); w[i].clear();
        }//初始化
        for(int i=;i<=m;i++){
            cin>>s1>>s2;
            scanf("%d",&dist);
            if(M[s1]==)M[s1]=++tot;
            if(M[s2]==)M[s2]=++tot;
            a=M[s1]; b=M[s2];
            e[a].push_back(b);
            w[a].push_back(dist);
        }//字元串讀入
        for(int i=;i<=tot;i++)dis[i]=;
        cin>>s1>>s2;
        if(M[s1]== || M[s2]==){//如果未出現過，肯定不能到達。
            printf("-1\n");
            continue;//我寫成break爆了3次
        }
        s=M[s1]; E=M[s2];
        node.d=; node.id=s; node.me=; q.push(node); dis[s]=;
        while(!q.empty()){
            if(dis[q.top().id]!=q.top().d)q.pop();//代替vis數組
            if(q.empty())break;
            node=q.top(); q.pop();
            u=node.id; di=node.d; Me=node.me;
            for(int i=;i<e[u].size();i++){
                if(w[u][i]>=Me && dis[u]+w[u][i]/+(Me+)/<dis[e[u][i]]){
                    dis[e[u][i]]=dis[u]+w[u][i]/+(Me+)/;
                    node.id=e[u][i];
                    node.d=dis[e[u][i]];
                    node.me=w[u][i];
                    q.push(node);
                }//新的最大邊權
                if(w[u][i]<Me && dis[u]+w[u][i]<dis[e[u][i]]){
                    dis[e[u][i]]=dis[u]+w[u][i];
                    node.id=e[u][i];
                    node.d=dis[e[u][i]];
                    node.me=Me;
                    q.push(node);
                }//照常處理
            }
        }
        if(dis[E]==)printf("-1\n");//不能到達，輸出-1
        else printf("%lld\n",dis[E]);//輸出距離
    }
}
           

完結撒花~謝謝大家~