Algoogle

Algorithm for Programming Contest

PKU 3615 Cow Hurdles

Category: PKU Tag: warshall-floyd

Cow Hurdles

問題概要


解法


N <= 300なのでWarshall-Floydで回します.
T <= 40000なので毎回Dijkstraとかすると間に合わないかもしれない.
普通のグラフの問題と違って距離の和ではなく, 高さのmaxを取っていく.

コード


(3615.cpp) download
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
#include <cstdio>
#include <queue>
#include <vector>
#include <map>
#include <cstring>
#include <algorithm>

using namespace std;

typedef pair<int,int> pii;

int N, M, T;
int H[310][310];

int main(){
    scanf("%d%d%d", &N, &M, &T);

    for(int i = 0; i < N; i++)
        for(int j = 0; j < N; j++)
            H[i][j] = int(1e9);

    for(int i = 0; i < M; i ++){
        int a, b, h;
        scanf("%d%d%d", &a, &b, &h);
        a--; b--;
        H[a][b] = h;
    }
    for(int k = 0; k < N; k++)
        for(int i = 0; i < N; i++)
            for(int j = 0; j < N; j++)
                H[i][j] = min(H[i][j], max(H[i][k], H[k][j]));

    while(T--){
        int s, t;
        scanf("%d%d", &s, &t);
        s--; t--;
        if(H[s][t] == int(1e9)) puts("-1");
        else printf("%d\n", H[s][t]);
    }
    return 0;
}

Comments