AOJのGRL_1_Aを解く（C）

PC

　どう転んでも例の10万円が我が家には来ないらしいことがわかりました。
　つまり耐乏生活は続くのです。休日といえどもお金のかかる娯楽はもってのほか。昼はCGCの安売りパスタでお腹を膨らませ、午後はお金のかからない趣味……そうプログラミングです。やりましょう、プログラミングやりましょう。

　というわけで、お題は2年ぶりぐらいに訪れましたAOJのGRL_1_A/Single Source Shortest Pathです。
　最短経路探索の基本問題とか紹介されてたんですが、問題文を読んでも全く訳が分かりません;-o-)仕方なくWikipediaのダイクストラ法の項に記されていた疑似コードとやらを翻訳していきます。言語はCです。たまたまCの本が部屋に転がっていたからですけども、何回やってもscanfの&を付け忘れるのでたぶん私には向いてません。
　（苦節2時間経過）ついにそれっぽいコードができました。提示されていた入力例に対し正しい答えが得られましたので勇んで提出してみたものの、残念なことにタイムアウト;-o-)どうもWikipediaの疑似コードにおける集合Q（解が未確定である頂点……たぶん）の管理がアホみたいに重すぎるのが原因のようです。もうこれ以上はわからないので仕方なく他所様が提出されたコードからヒントを探します。
　（さらに10分経過）なんとなくわかりました。面倒なQの管理をバッサリ省いて提出したところ、ついにACが得られました。
　コードがこちら。

#include <stdio.h>

int main(void) {

    int V,E,r,s[500000],t[500000],d[500000];
    int ans[100000];
    int i,flg;

    scanf("%d %d %d", &V, &E, &r);

    for (i=0;i<E;i++) {
        scanf("%d %d %d", &s[i], &t[i], &d[i]);
    }

    for (i=0;i<V;i++) {
        ans[i]=1e9;
    }

    ans[r]=0;

    while (1) {
 
        flg=0;
        for (i=0;i<E;i++) {
            if (ans[s[i]]+d[i]<ans[t[i]]) {
                ans[t[i]]=ans[s[i]]+d[i];
                flg=1;
            }
        }

        if (flg==0) break;
    }

    for (i=0;i<V;i++) {
        if (ans[i]==1e9) {
            puts("INF");
        } else {
            printf("%d\n", ans[i]);
        }
    }

    return 0;
}

　重要なのはWhile文の内部だけで、その前は初期化、その後は回答の表示に過ぎません。
　そのWhile文の要点はこうです。

  1. 　すべての辺の情報を読み出し、解（配列ans=各頂点に至る最小コスト）を更新できる頂点については更新する
  2. 　1.により解が更新される頂点が1つでも存在していたなら1.に戻る。なかったなら最終解に達しているので終了（回答の表示に移る）

　回答の桁数がintで足りているのかよくわからなかったり気になるところはありますが、ACになったのでもう考える気力が起きません。釣った魚にエサはやらないスタイル;-o-)

accs2014 読者になる

コメントを書く