正文之前

今天考完了！我可以很確定自己最多200分吧祈秕！第三題死活不記得那個(gè)星期幾轉(zhuǎn)換成年月日的算法了渺贤！所以第三題寫了一個(gè)小時(shí)結(jié)果最后卡死在哪兒動(dòng)不了！mmp 總共四個(gè)小時(shí)请毛，前面一個(gè)半小時(shí)解決了一二題志鞍，結(jié)果第三題一個(gè)小時(shí)浪費(fèi)了。第四題的圖論算法方仿，我看出來(lái)了是Dijkstra 算法 的變種固棚，但是最后還是沒(méi)能靈活的使用這個(gè)算法，所以就算把Dijkstra解決了仙蚜。但是還是沒(méi)法做到完成區(qū)分（我覺(jué)得已經(jīng)寫出來(lái)了按酥蕖！委粉！但是排完bug 編譯無(wú)錯(cuò)的時(shí)候已經(jīng)5：25了呜师。最后都沒(méi)交卷，只提交了代碼＜纸凇汁汗！煩躁Ｖ云琛！）

正文

具體的想法來(lái)自下面這篇寫的很好的博客知牌，當(dāng)然祈争，他的代碼很復(fù)雜，不如我的精簡(jiǎn)角寸，但是解釋這個(gè)算法的手法比我好得多菩混！

不多說(shuō)，我直接盜圖（圖片和我的代碼不相關(guān)扁藕，僅用于說(shuō)明算法）：

從上圖看的出來(lái)墨吓，每個(gè)節(jié)點(diǎn)與我們?cè)O(shè)置的出發(fā)節(jié)點(diǎn)1有下列的距離關(guān)系：

初始的時(shí)候，有的完全不相連纹磺，設(shè)置為無(wú)窮大，相連的就給出距離亮曹，此時(shí)的時(shí)候橄杨，我們只知道1節(jié)點(diǎn)是1節(jié)點(diǎn)的最短路徑，當(dāng)然也就是0距離了照卦。其他的都是未知最短路徑Ｊ浇谩！注意Ｒ鄹采转！注意！瞬痘！敲黑板９蚀取！ 我們一直有一個(gè)數(shù)組框全，數(shù)組大小等同于節(jié)點(diǎn)數(shù)察绷，每個(gè)元素都是bool變量，如果下標(biāo)所對(duì)應(yīng)的節(jié)點(diǎn) 比如1節(jié)點(diǎn)津辩，已知到1的最短路徑拆撼，那么bool變量為true；否則為false喘沿，把所有的節(jié)點(diǎn)分為兩個(gè)集合闸度，一種是已知最短路徑的節(jié)點(diǎn)集合，一種是未知的節(jié)點(diǎn) 的集合蚜印。

下面進(jìn)入正題莺禁， Dijkstra算法的進(jìn)程。 首先是尋找跟1節(jié)點(diǎn)相連的距離最短的未知（要求這個(gè)節(jié)點(diǎn)的bool變量為 false窄赋，否則就跳過(guò)）節(jié)點(diǎn)u睁宰， 找到后把他放到已知最短路徑的集合里面肪获，這是肯定的好不，其他的要不就是不相連柒傻，要不就是更短孝赫，所以從1出發(fā)的下一節(jié)點(diǎn)就肯定是這次找到的u。然后再環(huán)顧其他沒(méi)確定的節(jié)點(diǎn)红符，如果通過(guò)u到1的距離比它原來(lái)到1的距離還短青柄，那么就設(shè)置它的父節(jié)點(diǎn)是u，并且設(shè)置它到1的距離等于它到u的距離加上u到1的距離预侯。這樣在最后當(dāng)我們從這個(gè)節(jié)點(diǎn)到1的時(shí)候致开，就不會(huì)走原來(lái)的跟1直連的路（或者根本就不通），而是繞道u 走最短路徑萎馅。然后双戳，循環(huán)往復(fù)上面的過(guò)程，最后就可以所有的節(jié)點(diǎn)就有了一個(gè)前驅(qū)節(jié)點(diǎn)糜芳，有了一個(gè)到1節(jié)點(diǎn)的最短距離飒货。這個(gè)時(shí)候，我們需要哪個(gè)節(jié)點(diǎn)到1的距離峭竣，就等于它在上述算法中得到的距離塘辅，如果要找路徑，只需要對(duì)前驅(qū)節(jié)點(diǎn)進(jìn)行壓棧皆撩，然后拋出就可以得到了？鄱铡！

下面的代碼來(lái)自下面的CCF試題：

• 問(wèn)題描述
  　　G國(guó)國(guó)王來(lái)中國(guó)參觀后扛吞，被中國(guó)的高速鐵路深深的震撼呻惕，決定為自己的國(guó)家也建設(shè)一個(gè)高速鐵路系統(tǒng)。
  　　建設(shè)高速鐵路投入非常大滥比，為了節(jié)約建設(shè)成本蟆融，G國(guó)國(guó)王決定不新建鐵路，而是將已有的鐵路改造成高速鐵路∈匚兀現(xiàn)在型酥，請(qǐng)你為G國(guó)國(guó)王提供一個(gè)方案，將現(xiàn)有的一部分鐵路改造成高速鐵路查乒，使得任何兩個(gè)城市間都可以通過(guò)高速鐵路到達(dá)弥喉，而且從所有城市乘坐高速鐵路到首都的最短路程和原來(lái)一樣長(zhǎng)。請(qǐng)你告訴G國(guó)國(guó)王在這些條件下最少要改造多長(zhǎng)的鐵路玛迄。

• 輸入格式
  　　輸入的第一行包含兩個(gè)整數(shù)n, m由境，分別表示G國(guó)城市的數(shù)量和城市間鐵路的數(shù)量。所有的城市由1到n編號(hào)，首都為1號(hào)虏杰。
  　　接下來(lái)m行讥蟆，每行三個(gè)整數(shù)a, b, c，表示城市a和城市b之間有一條長(zhǎng)度為c的雙向鐵路纺阔。這條鐵路不會(huì)經(jīng)過(guò)a和b以外的城市瘸彤。

• 輸出格式
  　　輸出一行，表示在滿足條件的情況下最少要改造的鐵路長(zhǎng)度笛钝。

• 樣例輸入
  4 5
  1 2 4
  1 3 5
  2 3 2
  2 4 3
  3 4 2

• 樣例輸出
  11

• 評(píng)測(cè)用例規(guī)模與約定
  　　對(duì)于20%的評(píng)測(cè)用例质况，1 ≤ n ≤ 10，1 ≤ m ≤ 50玻靡；
  　　對(duì)于50%的評(píng)測(cè)用例结榄，1 ≤ n ≤ 100，1 ≤ m ≤ 5000囤捻；
  　　對(duì)于80%的評(píng)測(cè)用例臼朗，1 ≤ n ≤ 1000，1 ≤ m ≤ 50000蝎土；
  　　對(duì)于100%的評(píng)測(cè)用例视哑，1 ≤ n ≤ 10000，1 ≤ m ≤ 100000瘟则，1 ≤ a, b ≤ n，1 ≤ c ≤ 1000枝秤。輸入保證每個(gè)城市都可以通過(guò)鐵路達(dá)到首都醋拧。

#include<iostream>
using namespace std;

#define  The_Bigest_Num  1000000
#define BIGEST  10000
int Tu[BIGEST][BIGEST];
bool Judge_IF_IS_IN_MIN[BIGEST];
int Distance[BIGEST];
int Qian_Qu[BIGEST];

void dijkstra(int v0,int n)
{
    for(int i=1;i<=n;++i)
    {
        Judge_IF_IS_IN_MIN[i]=false;
        Distance[i]=Tu[v0][i];
        if(Distance[i]!=The_Bigest_Num)
            Qian_Qu[i]=v0;
        else
            Qian_Qu[i]=-1;
    }
    Distance[v0]=0;
    Judge_IF_IS_IN_MIN[v0]=true;
    for(int i=2;i<=n;++i)
    {
        int mind=The_Bigest_Num;
        int u=v0;
        for(int j=1;j<=n;++j)
        {
            if(!Judge_IF_IS_IN_MIN[j] && Distance[j]<mind)
            {
                u=j;
                mind=Distance[j];
            }
        }
        Judge_IF_IS_IN_MIN[u]=true;
        int minQianQu=The_Bigest_Num;
        for(int j=1;j<=n;++j)
        {
            if(!Judge_IF_IS_IN_MIN[j] && Tu[u][j]<minQianQu)
            {
                if(Distance[j]>=Distance[u]+Tu[u][j])
                {
                    Distance[j]=Distance[u]+Tu[u][j];
                    Qian_Qu[j]=u;
                    minQianQu= Tu[u][j];
                }
            }
        }
    }

    int all=0;
    for(int i=2;i<=n;++i)
    {
        if(Qian_Qu[i]!=1)
        {
            all+=(Distance[i]-Distance[Qian_Qu[i]]);
        }
        else
            all+=Distance[i];
    }
    cout<<all<<endl;
}


int main()
{
    int lines,size;
    cin>>size>>lines;
    for(auto &x:Tu)
        for(auto &s:x)
            s=The_Bigest_Num;
    while(lines--)
    {
        int a,b,c;
        cin>>a>>b>>c;
        Tu[a][b]=c;
        Tu[b][a]=c;
    }
    dijkstra(1,size);
}

運(yùn)行結(jié)果如下：

Last login: Sun Dec  3 23:23:59 on ttys000
HustWolf:~ zhangzhaobo$ /Users/zhangzhaobo/program/C++/Dijkstra ; exit;
4 5
1 2 4
1 3 5
2 3 2
2 4 3
3 4 2
11
logout
Saving session...
...copying shared history...
...saving history...truncating history files...
...completed.
Deleting expired sessions...3 completed.

[進(jìn)程已完成]

正文之后

走了走了。睡覺(jué)淀弹，妹子來(lái)了睡眠有保障５ず尽（我是說(shuō)睡得安心，舒爽） 剛給老師說(shuō)想去實(shí)驗(yàn)室薇溃，估計(jì)后面就會(huì)變方向了 ~ 希望自己不忘初心吧菌赖，簡(jiǎn)書暫時(shí)還是別??，我還想玩幾年~~