ICPC2006 アジア地区予選 Enjoyable Commutation

問題概要

　グラフ(V, E)が与えられる。a ∈ Vからb∈Vまでの経路のうちk番目に短い経路を生成せよ。ただし、1つの経路内で同じ節点を2回以上通ってはいけない。同じ長さの経路が2つ以上ある場合は、通過する節点を順番に並べたときに辞書順最小のものが一番短い経路であると判断する。

　2 ≦ n ≦ 50
　0 ≦ m ≦n(n-1)
　1 ≦ k ≦ 200

方針

　k-th shortest pathという典型問題。基本的にはダイクストラの要領でパスを生成していって、A*探索みたいな感じで最終的にえられるパスの長さの下限が小さいものから吸い上げていけばいい。
　ややこしいのが、同じ節点を複数回通ってはいけないという制約。ビットマスクで訪れた点を持っておきパス生成のときまだ訪れていない節点のみに遷移するのは当然やるとして、これに加えてそこからゴールにたどり着くまでの下限値も変化することに注意。よって、毎回priority_queueからpopされた状態におけるグラフ形状でダイクストラをしてゴールまでのパスの長さの下限値を出すというようなことをやってみた。グラフの形状が変化しなければ（同じ節点を何度通ってもいいならば）、最初にゴールから逆方向にダイクストラをすれば経路の下限は出るが、今回の場合はそのやり方だと精度の悪い下限値が出てしまい現実的な時間で計算が完了しないケースがあった。A*は評価関数の精度がいいほど速く計算できるが、今回もそれと同じだなと思った。
　あと、プラスα的な高速化として、すでにk回popされた節点にはもうpushしないようにするということをした。

※追記2012/04/19 この問題がPOJ(problem 3137)に登録されているのを発見しました。submitしたらTLEでした。さらなる高速化が必要なようです。

ソースコード

　スパゲッティなソースを載せておきます。

#include <iostream>
#include <vector>
#include <queue>
#include <sstream>
#include <cstring>

using namespace std;

struct edge {
    int to;
    int cost;
};

typedef pair<int, int> PII;
const int MAX_V = 50;
const int INF = (int)1e9;

int V;
vector<edge> G[MAX_V];
int dist[MAX_V];

/*
 * s: starting point
 * t: ending point
 */
void dijkstra(int s, int t, long long vis) {
    priority_queue<PII, vector<PII>, greater<PII> > Q;
    fill(dist, dist+V, INF);
    dist[s] = 0;
    Q.push(PII(0, s));

    while(!Q.empty()) {
        int d = Q.top().first;
        int v = Q.top().second;
        Q.pop();

        if (d > dist[v]) continue;
        if (v == t) return;

        for (int i = 0; i < (int)G[v].size(); i++) {
            int to = G[v][i].to;
            int cost = G[v][i].cost;

            if (d + cost < dist[to] && !(vis & 1LL << to)) {
                dist[to] = d + cost;
                Q.push(PII(dist[to], to));
            }
        }
    }
}

class Status {
public:
    int v;
    int len;
    int lb;
    long long vis;
    vector<int> path;

    Status(int v, int len, long long vis, vector<int>path, int goal) {
        this->v = v;
        this->len = len;
        this->vis = vis;
        dijkstra(v, goal, vis);
        this->lb = min(INF, len + dist[goal]);
        this->path = path;
    }

    bool operator>(const Status &v) const {
        if (this->lb != v.lb)
            return this->lb > v.lb;
        return this->path > v.path;
    }
};

int cntVis[MAX_V];
vector<int> kthShortestPath(int s, int t, int k) {
    priority_queue<Status, vector<Status>, greater<Status> > Q;
    vector<int> path;
    path.push_back(s);
    Q.push(Status(s, 0, 1LL<<s, path, t));
    memset(cntVis, 0, sizeof(cntVis));
    int m = 0;

    while (!Q.empty()) {
        int v = Q.top().v;
        int len = Q.top().len;
        long long vis = Q.top().vis;
        vector<int>path = Q.top().path;
        Q.pop();

        ++cntVis[v];
        if (v == t) {
            if (++m == k)
                return path;
            continue;
        }

        path.push_back(-1);
        for (int i = 0; i < (int)G[v].size(); i++) {
            int to = G[v][i].to;
            int cost = G[v][i].cost;

            if (!(vis & 1LL<<to) && cntVis[to] < k) {
                path.back() = to;
                Q.push(Status(to, len+cost, vis|1LL<<to, path, t));
            }
        }
    }

    return vector<int>();
}

int main() {
    int n, m, k, a, b;
    int x, y, d;

    while (cin >> n >> m >> k >> a >> b) {
        if (n+m+k+a+b == 0)
            break;

        --a;
        --b;
        V = n;

        // construct a graph
        for (int i = 0; i < V; i++)
            G[i].clear();
        for (int i = 0; i < m; i++) {
            cin >> x >> y >> d;
            G[--x].push_back((edge){--y, d});
        }

        vector<int> ret = kthShortestPath(a, b, k);
        if (ret.empty())
            cout << "None" << endl;
        else {
            stringstream ss;
            for (int i = 0; i < (int)ret.size(); i++) {
                if (i) ss << "-";
                ss << ret[i]+1;
            }
            cout << ss.str() << endl;
        }
    }

    return 0;
}