AOJ 1169 The Most Powerful Spell

問題概要

N頂点A辺からなる重み付き有向グラフがあり、各辺の重みは文字列で与えられます。始点から終点への文字列が辞書順で最小になるような経路を選んだときのその文字列を出力してください。ただし始点から終点への経路が存在しない、または無制限に辞書順で小さくできる場合はNOを出力してください。

問題リンク: The Most Powerful Spell | Aizu Online Judge

制約

• 2 ≦ N ≦ 40
• 0 ≦ A ≦ 400
• 0 ≦ s, g, x_i, y_i < N
• s ≠ g
• 1 ≦ |lab_i| ≦ 6

解法

直観的な解法として始点から辞書順最小の辺を貪欲に選んでいく方法が考えられますが一般には上手くいきません。行き止まりなる可能性や最小でない辺を選ぶほうが結果的に辞書順最小になるケースがあります。

実はこの問題を最短経路問題ととらえることができます。最短経路のアルゴリズムであるダイクストラ法やベルマン・フォード法は辺の重みに対して

min(x, y) + z = min(x+z, y+z)

が成立するようなとき使えます。(ある頂点への最短経路はその他のある頂点への最短経路に辺の重みを加えた形になっている)

ところが文字列辞書順の場合、上の式は成立しません。

min("a","ab") + c = "ac" ≠ "abc" = min("a"+"c","ab"+"c")

しかし、逆から足した

z + min(x, y) = min(z+x, z+y)

は成立します。

つまり、終点から始点に向かってならば最短経路アルゴリズムが使えます。

ただしダイクストラ法は使えません(辺を使った結果元よりも辞書順で小さくなることがあり、これが負の辺に相当するため)

参考サイト

この記事の内容は次のサイトの内容を参考にさせていただきました。

https://topcoder.g.hatena.ne.jp/cafelier/20100703

Code

#include <bits/stdc++.h>
using namespace std;

const string INF = "NO";

struct edge {
    int from, to;
    string s;
};

int n, a, s, g;
vector<edge> es;

string bellman_ford() {
    vector<string> d(n, INF);
    d[g] = "";
    for (int i = 0; i < 7 * n; i++) {
        for (auto e : es) {
            if (d[e.to] != INF && (d[e.from] == INF || d[e.from] > e.s + d[e.to])) {
                d[e.from] = e.s + d[e.to];
                if (i > n && e.from == s) return INF;
            }
        }
    }
    return d[s];
}

int main() {
    while (1) {
        cin >> n >> a >> s >> g;
        if (n == 0) break;
        es.clear();
        for(int i = 0; i < a; i++) {
            int x, y;
            string lab;
            cin >> x >> y >> lab;
            es.push_back({x, y, lab});
        }
        cout << bellman_ford() << endl;
    }
    return 0;
}