Problem A

Asterix and Obelix

Input: standard input

Output: standard output

Time Limit: 5 seconds

Memory Limit: 32 MB

After winning a gruesome battle against the Romans in a far-away land, Asterix and his dearest friend Obelix are now returning home. However Obelix is not with Asterix now. He has left Asterix in order to deliver menhir to one of his international buyers (as you probably know, recently he has extended his trade to international markets). But he has promised to join Asterix on his way home and Asterix has promised to host a feast for Obelix (you know how fat he is!) in the city they meet. Obelix may meet Asterix in any city on his way home including the starting and the destination city.

Now Asterix is sitting with a map and trying to figure out the cheapest route home. The map shows the cities and the cost (in sestertii) of going from one city to another if there is a road connecting them directly. For each city in the map Asterix has also calculated the cost (in sestertii) of hosting a feast for Obelix in that city. There will be only one feast and for safety Asterix has decided to set aside enough sestertii to host a feast in the costliest city on the route.

Since Asterix does not have a computer, he seeks your help to find out the cheapest route home.

Input

The input may contain multiple test cases.

The first line of each test case contains three integers C (£ 80), R (£ 1000) and Q (£ 6320) where C indicates the number of cities (cities are numbered using distinct integers ranging from 1 to C), R represents the number of roads and Q is the number of queries.

The next line contains C integers where the i-th integer f_i is the cost (in sestertii) of hosting a feast in city i.

Each of the next R lines contains three integers: c₁, c₂ (¹ c₁) and d indicating that the cost of going from city c₁ to c₂ (or from c₂ to c₁) is d sestertii.

Each of the next Q lines contains two integers c₁ and c₂ (c₁ ¹ c₂) asking for the cost (in sestertii) of the cheapest route from city c₁ to city c₂.

The input will terminate with three zeros form C, S and Q.

Output

For each test case in the input first output the test case number (starting from 1) as shown in the sample output. Then for each query in the input print a line giving the minimum cost (in sestertii) of going from the first to the second city in the query. If there exists no path between them just print “–1”.

Print a blank line between two consecutive test cases.

Sample Input

7 8 5

2 3 5 15 4 4 6

1 2 20

1 4 20

1 5 50

2 3 10

3 4 10

3 5 10

4 5 15

6 7 10

1 5

1 6

5 1

3 1

6 7

4 4 2

2 1 8 3

1 2 7

1 3 5

2 4 8

3 4 6

1 4

2 3

0 0 0

Sample Output

Case #1

45

-1

45

35

16

Case #2

18

20

(World Finals Warm-up Contest, Problem Setter: Rezaul Alam Chowdhury)

題目描述：

// 網上已經提供很多翻譯

每个城市举办庆祝有一定的花费，A在路径上会选择庆祝花费最大的城市      

让你求，A回家所花的路费和庆祝费最少，也就是说并不是最短路径就是结果，      

还有可能就是路费比最短路径的多，但是庆祝费就比它的少，总的加起来可能更小。

題目解法：

將點重新編號，根據舉辦宴會花費由小到大排序。

根據 floyd 的特性，保證當前路徑中不會有花費更大的地點，從花費小的地點依序加入計算最短路徑。

每一次迭代，去查找會經過該點的所有最短路徑，並且更新所有答案。

O(V^3) 簡單好寫，比網上很多複雜的 dijkstra 容易許多。

#include <stdio.h>
#include <algorithm>
#include <vector>
using namespace std;

int main() {
    int n, m, q;
    int cases = 0;
    int i, j, k, x, y, d;
    int f[105], g[105][105];
    while(scanf("%d %d %d", &n, &m, &q) == 3 && n) {
        vector< pair<int, int> > AT;
        int trans[105];
        for(i = 1; i <= n; i++) {
            scanf("%d", &f[i]);
            AT.push_back(make_pair(f[i], i));
        }
        sort(AT.begin(), AT.end());
        for(i = 0; i < AT.size(); i++)
            trans[AT[i].second] = i;
        int q_ret[105][105];
        for(i = 0; i < n; i++) {
            for(j = 0; j < n; j++)
                g[i][j] = 0xfffffff, q_ret[i][j] = 0xfffffff;
            g[i][i] = 0;
        }
        for(i = 1; i <= m; i++) {
            scanf("%d %d %d", &x, &y, &d);
            x = trans[x];
            y = trans[y];
            g[x][y] = g[y][x] = min(g[y][x], d);
        }
        for(k = 0; k < n; k++) {
            for(i = 0; i < n; i++)
                for(j = 0; j < n; j++)
                    g[i][j] = min(g[i][j], g[i][k] + g[k][j]);
            for(i = 0; i < n; i++) {
                for(j = 0; j < n; j++) {
                    if(g[i][k] + g[k][j] == g[i][j]) {
                        int val = AT[k].first;
                        val = max(val, AT[i].first);
                        val = max(val, AT[j].first);
                        q_ret[i][j] = min(q_ret[i][j], g[i][j] + val);
                    }
                }
            }
        }
        if(cases)    puts("");
        printf("Case #%d\n", ++cases);
        while(q--) {
            scanf("%d %d", &x, &y);
            x = trans[x];
            y = trans[y];
            if(q_ret[x][y] == 0xfffffff)
                puts("-1");
            else
                printf("%d\n", q_ret[x][y]);
        }
    }
    return 0;
}