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算法，希望之后做的小伙伴们不要在这个地方再中他的陷阱，浪费自己宝贵的时间