Algoogle

Algorithm for Programming Contest

AOJ 0526 Boat Travel

Category: AOJ Tag: warshall-floyd

Boat Travel

問題概要


解法


愚直に毎回warshall-floydでやるとTLEで死ぬ.
2点間のパスを渡されたら, そのパスがすでに作られてるパスで行くより大きかったら捨てる.
あとはその2点を中継点としとした場合を含めて各点への最短路を考えればいい.
これでwarshall-floydの一回目のループを2回だけにできる.

コード


(0526.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
#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;
#define rep(i, b) for(int i = 0; i < b; i++)
typedef vector<int> vec;
typedef vector<vec> mat;

#define INF 100000000

int main(){
    int n, k;
    while(cin>>n>>k,n||k){
        mat dist(n+1,vec(n+1,INF));
        while(k--){
            int t;
            cin >> t;
            if(t){
                int c[2], e;
                cin >> c[0] >> c[1] >> e;
                dist[c[0]][c[1]] = min(dist[c[0]][c[1]],e);
                dist[c[1]][c[0]] = min(dist[c[1]][c[0]],e);
                rep(k,2)rep(i,n+1)rep(j,n+1){
                    dist[i][j] = min(dist[i][j],dist[i][c[k]]+dist[c[k]][j]);
                }
            }else{
                int a, b;
                cin >> a >> b;
                cout << ((dist[a][b]==INF)? -1:dist[a][b]) << endl;
            }
        }
    }
}

Comments