aoj 0526 - Boat Travel

問題

問題概要

連続したクエリの中に頂点とそれをつなぐ辺の長さのクエリと、2点間の最短距離を求めよというクエリが含まれる。

解法

任意の2点間の距離を求めるにはワーシャルフロイト法で求めることができる。ただし、最短経路を求めよというクエリに対して毎回、ワーシャルフロイト法を行う必要はなく、2点間のん最短距離が更新れた時のみ行えばいいので、その情報をkousinnflagに持っておく。

ミス

ワーシャルフロイト法を呼び出しても意味がないときに呼び出してTLE(5sぐらい)した。

//TLE解
int main(void){
    while(1){
        int n, k;
        scanf("%d %d", &n, &k);
        if(n == 0 && k == 0) return 0;
        int dist[101][101];
        rep(i, 101) rep(j, 101){
            if(i == j) dist[i][j] = 0;
            else dist[i][j] = INF;
        }

        int flag, a, b, c, d, e;
        rep(i, k){
            scanf("%d", &flag);
            if(flag == 0){
                scanf("%d %d", &a, &b);
                a--; b--;
                //ワーシャルフロイトで最短経路を更新する
                rep(m, n) rep(l, n) rep(j, n)
                    dist[l][j] = min(dist[l][j], dist[l][m] + dist[m][j]);
                if(dist[a][b] >= 1e8) printf("-1\n");//経路がないとき
                else printf("%d\n", dist[a][b]);
            }else{
                scanf("%d %d %d", &c, &d, &e);
                c--; d--;
                if(dist[c][d] > e) dist[c][d] = dist[d][c] = e;//さらにいい経路があれば更新
            }
        }
    }
    return 0;
}

コード

#include <iostream>
#include <algorithm>
#include <cstdio>
#include <cstdlib>
using namespace std;
#define rep(i,n) for(int i=0;i<(n);i++)
static const int INF = 1e8;

int main(void){
    while(1){
        int n, k;
        scanf("%d %d", &n, &k);
        if(n == 0 && k == 0) return 0;
        int dist[101][101];
        rep(i, 101) rep(j, 101){
            if(i == j) dist[i][j] = 0;
            else dist[i][j] = INF;
        }

        int flag, a, b, c, d, e;
        //何度もワーシャルフロイトを呼ぶのは無駄が多い
        int kousinnflag = false;//頂点間の距離が短いものに更新されたことを示すフラグ
        rep(i, k){
            scanf("%d", &flag);
            if(flag == 0){
                scanf("%d %d", &a, &b);
                a--; b--;
                //ワーシャルフロイトで最短経路を更新する　（前回ワーシャルフロイトを計算した後頂点間の距離が更新されてなければ計算する必要はない）
                if(kousinnflag == true){
                    rep(m, n) rep(l, n) rep(j, n)
                        dist[l][j] = min(dist[l][j], dist[l][m] + dist[m][j]);
                    kousinnflag = false;
                }

                if(dist[a][b] >= 1e8) printf("-1\n");//経路がないとき
                else printf("%d\n", dist[a][b]);
            }else{
                scanf("%d %d %d", &c, &d, &e);
                c--; d--;
                if(dist[c][d] > e){
                    dist[c][d] = dist[d][c] = e;//さらにいい経路があれば更新
                    kousinnflag = true;
                }
            }
        }
    }
    return 0;
}