第五周：( Sicily1031) Campus（c++）

想找一道Dijkstra’s algorithm算法的題，由于leetcode上面沒有相關的标簽，搜尋也不好搜，就找了sicily上面的一道題。許久沒做sicily上的題，兩個平台确實有所差異（leetcode不是純黑盒測試，會提示哪組樣例沒過），确實還真有點不習慣，一些常見的坑全被我跳進去了，交了20次左右，time limited和wrong answer好久，最後才找到了兩處小錯誤。

原題連結：http://soj.sysu.edu.cn/1031

思路：本題基本上就是裸的Dijkstra’s algorithm，算法原理這裡不贅述。卡題的原因總結如下：（1）time limited是因為

c--

這一句放在了while循環的最後面，導緻在某個樣例continue之後c一直沒有做

c--

，是以變成死循環。由于在找錯的過程中剛開始以為是算法的邏輯錯誤導緻某組樣例出現了死循環，是以一開始一直搞錯了方向（2）wrong answer是因為

cout<<"-1"<<endl

這一句，沒加雙引号，汗，一開始排錯的方向也一直是算法某些特殊樣例沒過。（3）其實本題還有一些情況需要考慮。比如圖可能不連通；比如，最後可能問的是a到a的距離；再比如，可能問的是a到z的距離，而z在前面沒出現過。這裡就不一一而足了。

代碼如下：

//C-- can't put at the last of while because of so many "continue" and "break"
//the output -1 and 0 must be outputted as "-1" and "0"
#include <iostream>
#include <string>
using namespace std;

int main(){
    int C;
    cin>>C;
    while(C>){
        //C-- can't put at the last of while because of so many "continue" and "break"
        C--;
        //v[201] stores the places 
        string v[];
        //distance[201][201] stores the distance between the places
        int distance[][];
        //nplace means the nums of places
        int nplace=;
        //res1,res2 represents the places which the program want to know the shortest distance between them 
        string res1,res2;
        int res_x=,res_y=;
        //initializate
        for(int i=;i<;i++){
            v[i]="";
            for(int j=;j<;j++)
                if(i==j)
                    distance[i][j]=;
                else
                    distance[i][j]=;
        }
        int len;
        int N;
        cin>>N;
        //store the places and distance between them, the string places are changed to int.
        while(N--){
            string a,b;
            cin>>a>>b>>len;
            int xi,yi;
            //flag1 and flag2 are flags to judge whether the place has appeared before
            bool flag1=false,flag2=false;
            for(int i=;i<=nplace;i++){
                if(v[i]==a){
                    xi=i;
                    flag1=true;
                }
                if(v[i]==b){
                    yi=i;
                    flag2=true;
                }
            }
            if(!flag1){
                nplace++;
                xi=nplace;
                v[nplace]=a;
            }
            if(!flag2){
                if(a!=b){
                    nplace++;
                    v[nplace]=b;
                }
                yi=nplace;
            }
            distance[xi][yi]=len;
            distance[yi][xi]=len;
        }

        cin>>res1>>res2;
        //find the index of res1 and res2 in v[201],if can't find it,res_x=0,res_y=0
        for(int i=;i<=nplace;i++){
            if(v[i]==res1)
                res_x=i;
            if(v[i]==res2)
                res_y=i;
        }
        //the same place
        if(res1==res2){
            cout<<"0"<<endl;
            continue;
        }
        //if the place res1 or res2 havn't appeared before, one of res_x,res_y must be 0 
        if((res_x==)||(res_y==))
        {
            cout<<"-1"<<endl;
            continue;
        }
        //Dijkstra's algorithm
        bool visited[];
        int pre;
        int res_x_to_others[];
        bool fg=false;
        for(int i=;i<;i++){
            res_x_to_others[i]=;
            visited[i]=false;
        }
        visited[res_x]=true;
        pre=res_x;
        res_x_to_others[res_x]=;
        for(int i=;i<=nplace;i++){
            int min=;
            //find the place which has the shortest distance
            for(int j=;j<=nplace;j++){
                if((!visited[j])&&(res_x_to_others[j]<min)){
                    min=res_x_to_others[j];
                    pre=j;
                }
            }
            //pre means the last place visit
            visited[pre]=true;
            //find out res2,cout the result
            if(pre==res_y){
                cout<<res_x_to_others[pre]<<endl;
                fg=true;
                break;
            }
            //update the distance
            for(int j=;j<=nplace;j++){
                if((!visited[j])&&(res_x_to_others[pre]+distance[pre][j]<res_x_to_others[j])){
                    res_x_to_others[j]=res_x_to_others[pre]+distance[pre][j];
                }
            }
        }
        //can't find res2 means res1 can't connect to res2
        if(!fg)
            cout<<"-1"<<endl;
    }
    return ;
}                                 
           

代碼确實寫得比較挫，也談不上什麼OO原則，一開始純粹就是想過題，習慣也不好。後面加了很多注釋以便了解。之後應該還會對這個算法進行總結和整理。