はじめてのk-th shortest path - 3255 Roadblocks - div1に上がりたいkeitanxkeitanの日記

1からNまでのパスの内、２番目に短いものを探す。

後で調べてわかったけどこれはk-th shortest pathという問題らしい。

そういえばアルゴリズムの講義でやった気もしないでもないけど、

とりあえずchokudaiくんの教えにしたがって、

アルゴリズムを知らなくても自分なりに考え取り組んでみた。

ダイクストラでは最短路を求めることしかできない。
でもダイクストラの考え方は使えそうだ。
更に考えると、ダイクストラはvisited[]やlabel[next] > curr.cost + edge.wなどの縛りが強いせいで（おかげで）最短路しか求められないのである。

これらの縛りをなくしてあげれば、while (!Q.empty())ループを回している限り、
パスを生成し続ける。（いつかはMLEだけど）

でもそれだけだと、２番目のパスを求めることはできない。
各パスはランダムな順序でゴールに至るため、いつまでループを回したらいいのかわからないのである。
そこで、何らかの形でpriority_queueに順序付けをしてやらなければならない。

そこで考えたのがゴールからの距離である。

通常のダイクストラの[それまでの距離]というソート基準に加えて
[ゴールまでの距離]を加えてやれば、priority_queueが、ゴールに近い状態から吐きだしてくれるため、最短路、２番目の最短路、３番目の最短路、、、という風に求められそうである。

ゴールまでの距離は普通にダイクストラで計算すればいい。

こんなことに気づいてしまうなんて、ちょっとできる子なんじゃないの（ニヤリ
としていたけど、きっと昔習ったのが頭の片隅にあっただけだろうな。。。

#include<cstdio>
#include<vector>
#include<queue>
#include<climits>
#include<cstring>

using namespace std;

struct State {
    int n, w;
    State(int n, int w) :
	n(n), w(w) {}
    bool operator < (const State &s) const {
	return w > s.w;
    }
};

struct Edge {
    int n, w;
    Edge (int n, int w) :
	n(n), w(w) {}
};

typedef vector<Edge> Edges;
typedef vector<Edges> Graph;

/*
 * ダイクストラみたいなアルゴリズムで
 * k番目に短いパスを求める
 * この問題では1-2-1-3のようなパスも許される
 * このようなパスを禁止するには、visited[]を用意して
 * 条件付きでcontinueを使い、
 * goalに着いたとき、visited[goal] = falseにしてやればよい
 * （ゴールに至る他のパスを探すため）
 */
int k_shortestPath(const Graph &g, int s, int e, int k) { // gはグラフ、sとeはスタートゴール
    int N = g.size();
    int dist[N];  // dist[i]はゴールからiまでの距離
    bool visited[N];
    for (int i = 0; i <= N; ++i) dist[i] = INT_MAX;
    dist[e] = 0;  // ゴールからゴールへの距離は0（これを入れ忘れてMLE連発した。。。）
    memset(visited, false, sizeof(visited));
    priority_queue<State> Q;
    // ゴールから各ノードへの距離を求める（普通のdijkstra）
    Q.push(State(e, 0));
    while (!Q.empty()) {
	State cr = Q.top(); Q.pop();
	if (visited[cr.n]) continue;
	visited[cr.n] = true;
	for (int i = 0; i < g[cr.n].size(); ++i) {
	    Edge edg = g[cr.n][i];
	    if (visited[edg.n]) continue;
	    if (dist[edg.n] > cr.w + edg.w) {
		dist[edg.n] = cr.w + edg.w;
		Q.push(State(edg.n, cr.w + edg.w));
	    }
	}
    }
    int cnt = 0; // ゴールカウント
    priority_queue<State> R;
    /* priority_queue Rは
     * [それまでの距離＋そのノードからゴールまでの距離]
     * でソートされる。
     * これによりゴールに近い状態から取り出される
     */
    R.push(State(1, 0 + dist[1])); 
    while (!R.empty()) {
	State cr = R.top(); R.pop();
	cr.w -= dist[cr.n]; // cr.wをそれまでの距離に戻す
	if (cr.n == e && ++cnt == k) return cr.w; // k回目にゴールしたらそれまでの距離を返す
	for (int i = 0; i < g[cr.n].size(); ++i) {
	    Edge edg = g[cr.n][i];
	    R.push(State(edg.n, cr.w + edg.w + dist[edg.n]));
	}
    }
    return -1;
}

int main() {
    int N, R;
    scanf("%d %d", &N, &R);
    Graph g(N + 1);
    for (int i = 0; i < R; ++i) {
	int A, B, D;
	scanf("%d %d %d", &A, &B, &D);
	g[A].push_back(Edge(B, D));
	g[B].push_back(Edge(A, D));
    }
    printf("%d\n", k_shortestPath(g, 1, N, 2));
}