Sicily---1031. Campus（最短路径）

注：搬运自我的csdn博客 http://blog.csdn.net/qq_30172585

题目如下：

Description
At present, Zhongshan University has 4 campuses with a total area of 6.17 square kilometers sitting respectively on both sides of the Pearl River or facing the South China Sea. The Guangzhou South Campus covers an area of 1.17 square kilometers, the North Campus covers an area of 0.39 square kilometers, the Guangzhou East Campus has an area of 1.13 square kilometers and the Zhuhai Campus covers an area of 3.48 square kilometers. All campuses have exuberance of green trees, abundance of lawns and beautiful sceneries, and are ideal for molding the temperaments, studying and doing research.

Sometime, the professors and students have to go from one place to another place in one campus or between campuses. They want to find the shortest path between their source place S and target place T. Can you help them?
Input
The first line of the input is a positive integer C. C is the number of test cases followed. In each test case, the first line is a positive integer N (0< N <=100) that represents the number of roads. After that, N lines follow. The i-th(1<=i<=N) line contains two strings Si, Ti and one integer Di (0<=Di<=100). It means that there is a road whose length is Di between Si and Ti. Finally, there are two strings S and T, you have to find the shortest path between S and T. S, T, Si(1<=i<=N) and Ti(1<=i<=N) are all given in the following format: str_Campus.str_Place. str_Campus represents the name of the campus, and str_Place represents the place in str_Campus. str_Campus is "North", "South", "East" or "Zhuhai". str_Place is a string which has less than one hundred lowercase characters from "a-z". You can assume that there is at most one road directly between any two places.

Output
The output of the program should consist of C lines, one line for each test case. For each test case, the output is a single line containing one integer. If there is a path between S and T, output the length of the shortest path between them. Otherwise just output "-1" (without quotation mark). No redundant spaces are needed.

分析：
A. 就是单源最短路径问题，这个很明显，可以选用Dijkstra算法求解
B. 数据规模0< N <=100，最多只有100*2 = 200 个顶点，数据量较小，可以用较为简单的邻接矩阵
C. 输入中给出的顶点是字符串，需要转化为对应的数字才能用邻接矩阵，此时可以用map< string,int >进行映射
D. 此题有坑——最后让你求的那两点可能与其他点都无路径相同，具体参看代码输出部分的判断语句

另附几个链接：
Dijkstra算法讲解
单源最短路径的动态演示

代码如下

#include<iostream>
#include<cstring>
#include<cstdlib>
#include<string>
#include<cstdio>
#include<algorithm>
#include<map>
using namespace std;

#define INF 0xfffff
const int SIZE = 210;

/*说明： 图中顶点集合V分成两组，第一组为已求出最短路径的顶点集合，简称“最短顶点集”
第二组为其余未确定最短路径的顶点集合 ，简称“未确定顶点集”
*/
int graph[SIZE][SIZE];//图的邻接矩阵 
int visited[SIZE];//visited[i] == 1表示顶点 i 已经加入最短顶点集
int min_length[SIZE];//min_length[i]储存的是当前源点到顶点i的最短长度 

int Dijkstra(int n, int source, int end)//n为顶点的总数 
{
    int now = source;//当前新加入最短顶点集的顶点，初始点为源点 

    int mid = 0, m_min = INF;/*m_min以及mid用于查找未确定顶点集中min_length值最小的顶点，
                             即下一个要加入最短顶点集的顶点 */

    int cnt = 0;
    while (cnt < n - 1)//将剩下的n-1个顶点都加入最短顶点集 
    {
        m_min = INF;
        for (int i = 1; i <= n; i++)
        {
            //对顶点now的邻接点进行更新 
            if (!visited[i] && min_length[now] + graph[now][i] < min_length[i])
            {
                min_length[i] = min_length[now] + graph[now][i];
            }
            //查找未确定顶点集中min_length值最小的顶点
            if (!visited[i] && m_min > min_length[i])
            {
                m_min = min_length[i];
                mid = i;
            }
        }
        now = mid;
        visited[mid] = 1;//min_length值最小的顶点加入最短顶点集 

        cnt++;
    }
    return min_length[end];
}

//初始化操作 
void initial()
{
    memset(visited, 0, sizeof(visited));

    for (int i = 0; i < SIZE; i++)
    {
        min_length[i] = INF;
        for (int j = 0; j < SIZE; j++)
        {
            graph[i][j] = INF;
            graph[j][i] = INF;
        }
    }
}



int main()
{
    int cases, n, len;
    string strA, strB;

    cin >> cases;
    while (cases--)
    {
        map<string, int> s2i;//s2i for "string to int"
        initial();
        int id = 0;
        cin >> n;
        while (n--)
        {
            int id_A = 0, id_B = 0;
            cin >> strA >> strB >> len;
            if (!s2i[strA])             //如果strA不在s2i里面
                id_A = s2i[strA] = ++id;
            else
                id_A = s2i[strA];
            if (!s2i[strB])             //如果strB不在s2i里面
                id_B = s2i[strB] = ++id;
            else
                id_B = s2i[strB];

            graph[id_A][id_B] = len;    //修改AB之间的长度
            graph[id_B][id_A] = len;
        }

        cin >> strA >> strB;
        int source = s2i[strA];
        int end = s2i[strB];
        visited[source] = 1;
        min_length[source] = 0;

        int shortest_len = Dijkstra(id, source, end);
        if (strA == strB)
            cout << 0 << endl;
        else if (shortest_len == INF || !s2i[strA] || !s2i[strB])
            cout << -1 << endl;
        else
            cout << shortest_len << endl;

    }
}