注：搬運自我的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. 數(shù)據(jù)規(guī)模0< N <=100，最多只有100*2 = 200 個頂點，數(shù)據(jù)量較小框咙，可以用較為簡單的鄰接矩陣
C. 輸入中給出的頂點是字符串绘盟，需要轉(zhuǎn)化為對應(yīng)的數(shù)字才能用鄰接矩陣，此時可以用map< string,int >進行映射
D. 此題有坑——最后讓你求的那兩點可能與其他點都無路徑相同谦去，具體參看代碼輸出部分的判斷語句

另附幾個鏈接：
Dijkstra算法講解
單源最短路徑的動態(tài)演示

代碼如下

#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 已經(jīng)加入最短頂點集
int min_length[SIZE];//min_length[i]儲存的是當前源點到頂點i的最短長度 

int Dijkstra(int n, int source, int end)//n為頂點的總數(shù) 
{
    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;

    }
}