sicily1031Campus之最短路徑解題報告

題目陷阱

昨天講了人工智能中的搜尋算法，貪婪算法，A*算法，爬山算法，模拟退火算法和遺傳算法，聽着好屌的樣子，其實也沒什麼，回來之後打算練習一個A*算法的執行個體，剛想做A*算法，發現前幾天講的最短路徑還沒有做，然後就在sicily上找到了這道題1031，本想着這道題木很容易，很快能做完然後再繼續A*算法，沒想到這題WA了我一晚上，看到其他人的結題報告才過了，現在對這個題目的最大的印象是

坑！坑！坑！

這題算法沒什麼使用的就是dijkstra算法求最短路徑，但是這題的測試樣例的确讓人很頭痛，先說一下這道題題目的陷阱：

* 當輸入的終點和原點相同時，輸出結果為０

* 輸入的兩個地點可能不在之前路徑提到的地點中，輸出-1

* 這題最坑的陷阱是在這裡，當兩個終點都不在之前提到的road裡面，但是兩個路徑又相同，這時會輸出結果不是-1而是０！！！

其實作在想想這題和實際情況還是挺接近的，但是在題目中硬是沒想出來

題目dijkstra算法描述

算法思想：

設G=(V,E)是一個帶權有向圖，把圖中頂點集合V分成兩組，第一組為已求出最短路徑的頂點集合（用S表示，初始時S中隻有一個源點，以後每求得一條最短路徑 , 就将加入到集合S中，直到全部頂點都加入到S中，算法就結束了），第二組為其餘未确定最短路徑的頂點集合（用U表示），按最短路徑長度的遞增次序依次把第二組的頂點加入S中。在加入的過程中，總保持從源點v到S中各頂點的最短路徑長度不大于從源點v到U中任何頂點的最短路徑長度。此外，每個頂點對應一個距離，S中的頂點的距離就是從v到此頂點的最短路徑長度，U中的頂點的距離，是從v到此頂點隻包括S中的頂點為中間頂點的目前最短路徑長度。

算法步驟：

a.初始時，S隻包含源點，即S＝{v}，v的距離為0。U包含除v外的其他頂點，即:U={其餘頂點}，若v與U中頂點u有邊，則<u,v>正常有權值，若u不是v的出邊鄰接點，則<u,v>權值為∞。

b.從U中選取一個距離v最小的頂點k，把k，加入S中（該標明的距離就是v到k的最短路徑長度）。

c.以k為新考慮的中間點，修改U中各頂點的距離；若從源點v到頂點u的距離（經過頂點k）比原來距離（不經過頂點k）短，則修改頂點u的距離值，修改後的距離值的頂點k的距離加上邊上的權。

d.重複步驟b和c直到所有頂點都包含在S中。

代碼

#include <iostream>
#include <map>
#include <cstring>

using namespace std;

#define MAX 210
#define MAX_NUM 200000
int Map[MAX][MAX];
bool visited[MAX];
int dis[MAX];

int main() {
    int test, n, d;
    string si, di;
    cin >> test;
    while (test--) {
        map<string, int> m;
        int index = , start, end;
        cin >> n;
        for (int i = ; i <  * n; i++)
            for (int j = ; j <  * n; j++) {
              if (i == j)
                  Map[i][j] = ;
              else
                  Map[i][j] = MAX_NUM;
            }
        for (int i = ;  i < n; i++) {
            cin >> si >> di >> d;
            if (m.find(si) == m.end()) {
                m.insert(pair<string, int>(si, index));
                start = index;
                index++;
            } else
                start = m[si];
            if (m.find(di) == m.end()) {
                m.insert(pair<string, int>(di, index));
                end = index;
                index++;
            } else
                end = m[di];
            Map[start][end] = d;
            Map[end][start] = d;
        }
        cin >> si >> di;
                //坑爹的樣例，還老子WA了一晚上，當輸入的地點不在所輸入的路徑裡時，若兩個地點相同，也輸出０
        if (si == di) {
            cout <<  << endl;
            continue;
        }
        if (m.find(si) == m.end() || m.find(di) == m.end()) {
          cout  << - << endl;
          continue;
        }
        start = m[si];
        end = m[di];

        memset(visited, false, sizeof(visited));
        for (int i = ; i < index; i++) {
            dis[i] = Map[i][start];
        }
        visited[start] = true;
        dis[start] = ;
        while () {
            int min = MAX_NUM, v;
            for (int i =  ; i < index; i++) {
                if (!visited[i] && min > dis[i]) {
                    min = dis[i];
                    v = i;
                }
            }
            if (min == MAX_NUM) break;
            visited[v] = true;
            for (int i = ; i < index; i++) {
                if (!visited[i] && Map[v][i] + min < dis[i])
                  dis[i] = Map[v][i] + min;
            }
        }

        if (dis[end] == MAX_NUM)
          cout << - << endl;
        else
          cout << dis[end] << endl;
    }
}
           

題目挺容易，直接dijkstra算法，希望之後做的小夥伴們不要在這個地方再中他的陷阱，浪費自己寶貴的時間