Morris' Blog 我在摸索我存在的意義、生命的意義、內涵及價值。 沒有真正神手般的厲害，套用模式是大部分的情況。 沒那麼厲害的我存在的意義為何，襯托出神的存在？ 有時候不能怪別人不給我機會，我已經開始省思， 為什麼我沒有給別人機會的原因，而是全要靠別人。 有時候我認為我與眾不同，那是因為我做不到很多人能辦到的事情。 我聽不到、玩不起來、說得不夠明瞭、理解得不夠多， 我缺少的語文能力，就是一切一切無能的判定。 為此，我不曉得能做些對別人有幫助的事情。 我知道我自己是個不服輸的性格，但現在我不得不認輸。 我沒有能力，因此我必須認輸。 我到底來這世界作什麼？處處充滿不確定性， 而我總是無法出類拔萃，想當個一般人似乎也回不了頭了。 越強大的挑戰需要越強力的支持，而我的支持是什麼？ 最近嘗試與人談話，但都是失敗的結局，沒人能接受， 不需要言語，不需要溝通，一切所想都表達不出來。

49愛的鼓勵 6訂閱站台

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;
}