[UVA] 11047 - The Scrooge Co Problem
The Scrooge Co Problem
| 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
1
C99 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;
}