The Scrooge Co Problem

The delivery company Scrooge Co. wants to establish a system to pay its employees the minimum money in their travels. The company has information about which the minimum cost to go from a location to another one is.

They ask you for getting a solution to compute the minimum amount of money that an employee will receive to go from one location to another one and which the route that he should use to arrive in is.

Input 

The input begins with a single integer 1C99 on a line by itself, indicating the number of test cases following, each of them as described below.

For each test case, the first line has an integer 1P99, indicating the number of locations we consider for this case. The second line gives us the name of each location separated by a TAB, each name has at most 20 characters.The next P lines contain the minimum cost to go from one location to another one separated by a TAB, the first line have the costs between the first location and the rest, the second line are the costs between the second location and the rest, and so on. A cost is an integer -1C300, where -1 means that is too expensive a travel between the locations, and 0 is used to indicate the cost from a location to the same location.

After the P lines there is an integer 1R99, indicating the number of routes that we have to consider. Following R lines containing the name of the employee, the start location and the end location. The locations names are case sensitive and the name of the employee has at most 30 characters.

Output 

For each test case you should produce one or two outputs line.

If a route between the locations exists, you will produce two lines, one with the cost and other with the path according to this format

``Mr < employeename > to go from < origname > to < destname >, you will receive < minimumcost > euros"

``Path: < origname > < locationsseparatedbyablank > < destname >"

If a route between the locations does not exist, you will produce one line, according to this format:

``Sorry Mr < employeename > you can not go from < origname > to < locname >"

Sample Input 

 
2
6
Ofi1	Ofi2	Ofi3	ofi4	ofi5	ofi6
0	4	1	-1	4	-1
4	0	-1	2	3	4
1	-1	0	-1	3	-1
-1	2	-1	0	-1	1
4	3	3	-1	0	2
-1	4	-1	1	2	0
1
emp1	Ofi1	ofi4
3
Murcia	Alicante	Albacete
0	3	-1
-1	0	4
-1	-1	0
2
Dofyl	Murcia	Albacete
Dofyl	Albacete	Murcia

Sample Output 

 
Mr emp1 to go from Ofi1 to ofi4, you will receive 6 euros
Path:Ofi1 Ofi2 ofi4
Mr Dofyl to go from Murcia to Albacete, you will receive 7 euros
Path:Murcia Alicante Albacete
Sorry Mr Dofyl you can not go from Albacete to Murcia

---

這題一樣要找最短路徑，並且把最短路徑輸出。

但是題目比較噁心，會問自己到自己，因此會比較麻煩。

因此處理的時候，改用 All-pair 的 Floyd 計算最短路徑。

#include <stdio.h>
#include <map>
#include <queue>
#include <string.h>
#include <iostream>
using namespace std;
int g[105][105], mid[105][105];
string site[105];
int main() {
    int n, q, testcase;
    char s[105], s2[105], name[105];
    scanf("%d", &testcase);
    int i, j, k;
    while(testcase--) {
        scanf("%d", &n);
        map<string, int> R;
        for(i = 0; i < n; i++) {
            scanf("%s", s);
            R[s] = i;
            site[i] = s;
        }
        for(i = 0; i < n; i++) {
            for(j = 0; j < n; j++) {
                scanf("%d", &g[i][j]);
                if(g[i][j] == -1)   g[i][j] = 0xfffffff;
                mid[i][j] = j;
            }
        }
        for(k = 0; k < n; k++) {
            for(i = 0; i < n; i++) {
                for(j = 0; j < n; j++) {
                    if(g[i][j] > g[i][k]+g[k][j])
                        g[i][j] = g[i][k] + g[k][j], mid[i][j] = mid[i][k];
                }
            }
        }
        scanf("%d", &q);
        while(q--) {
            scanf("%s %s %s", name, s, s2);
            int st = R[s], ed = R[s2];
            if(g[st][ed] == 0xfffffff)
                printf("Sorry Mr %s you can not go from %s to %s\n", name, s, s2);
            else {
                printf("Mr %s to go from %s to %s, you will receive %d euros\n", name, s, s2, g[st][ed]);
                printf("Path:");
                printf("%s", site[st].c_str());
                for(st = mid[st][ed]; st != ed; st = mid[st][ed])
                        printf(" %s", site[st].c_str());
                printf(" %s\n", site[ed].c_str());
            }
        }
    }
    return 0;
}