1031_Campus

题目链接：

http://soj.me/1031

题目大意：

给出四个校区的一些地点之间的距离，地点名用字符串来表示，问某两个地点之间的最短路径长度，典型的单源最短路径题目

思路：

单源最短路径问题可以用dijkstra算法实现，这道题比较麻烦的是用字符串来表示地点，我用的处理方法是建立map得到地点名字到序号的映射，对于每个新输入的地点名字，先在map里面查找是否存在，如果不存在就绑定一个新的序号．地点之间的距离用邻接矩阵来存放．

代码：

#include <iostream>#include <memory.h>#include <map>#include <queue>#include <vector>using namespace std;const int INF = 100000;int distances[300][300];int shortest[300];bool included[301];map<string, int> m;int numRoads;int numPlaces;string start_name, end_name;void input_and_init();int find_shortest();int find_nearest();int main() {    int numTestcases;    cin >> numTestcases;    while (numTestcases--) {        input_and_init();        if(start_name == end_name)            cout << 0 << endl;        else if(m.count(start_name) == 0 || m.count(end_name) == 0)            cout << -1 << endl;        else            cout << find_shortest() << endl;    }    return 0;}void input_and_init(){    cin >> numRoads;    numPlaces = 0;    m.clear();    for (int i = 0; i < 300; ++i) {        for (int j = 0; j < 300; ++j) {            distances[i][j] = (i == j ? 0 : INF);        }    }    memset(included, false, sizeof(included));    for (int i = 0; i < 300; ++i) {        shortest[i] = INF;    }    string s1, s2;    int d;    for (int i = 0; i < numRoads; ++i) {        cin >> s1 >> s2 >> d;        if(m.count(s1) == 0)            m[s1] = ++numPlaces;        if(m.count(s2) == 0)            m[s2] = ++numPlaces;        distances[m[s1]][m[s2]] = distances[m[s2]][m[s1]] = d;    }    cin >> start_name >> end_name;}int find_shortest(){    //Post: 如果起点和终点间有连通则返回最短路径长度，否则返回-1    int start = m[start_name], end = m[end_name];    shortest[start] = 0;    for (int i = 0; i < numPlaces; ++i) {        int cur = find_nearest();        included[cur] = true;        for (int j = 1; j <= numPlaces; ++j) {            if(!included[j]  && shortest[j] > shortest[cur] + distances[cur][j]){                shortest[j] = shortest[cur] + distances[cur][j];            }        }    }    if(shortest[end] < INF)        return shortest[end];    else        return -1;}int find_nearest(){    //返回当前离集合S最近的点的下标    int nearest_index = 0;    int shortestDistance = INF;    for (int i = 1; i <= numPlaces; ++i) {        if(shortest[i] < shortestDistance && !included[i]){            nearest_index = i;            shortestDistance = shortest[i];        }    }    return  nearest_index;}                                 

Sicily 1031. Campus 解题报告