人材獲得作戦の問題をWarshall-Floydで

人生を書き換える者すらいた。: 人材獲得作戦・４　試験問題ほかを今度はWarshall-Floydで解いてみた。

Dijkstraが特定の2点間の最短経路を求めるのに対して、Warshall-Floydは全ての2点間の最短経路を一括で求める。
またWarshall-Floydの良い点として、負辺の処理および負閉路の検出も可能ということが挙げられる。
負辺に対応した単一始点最短経路探索のBellman-Fordというのもあるようだけれど、Warshall-FloydのオーダーがO(|V|^3)なのに対してBellman-FordはO(|V||E|)らしいので、ある程度疎でない限りWarshall-Floydでいいんじゃないかな。

効率は悪いが、まあWarshall-Floydの練習ってことでどんまい。綺麗だし。

#include <iostream>
#include <string>
#include <vector>
#include <algorithm>
using namespace std;

int main(int argc, char **argv)
{
    size_t w = 0;
    vector<string> lines;
    while(!cin.eof()) {
        lines.push_back(string());
        getline(cin, lines.back());
        w = max(w, lines.back().size());
    }
    string maze;
    for(int i = 0; i < (int)lines.size(); i++) {
        lines[i].resize(w);
        maze.append(lines[i]);
    }
    int n = maze.size();
    vector<vector<int> > wf(n, vector<int>(n, 100000000));
    vector<vector<int> > wfl(n, vector<int>(n, -1));
    int s=-1,g=-1;
    for(int i = 0; i < n; i++) {
        if(maze[i]=='S')s=i;
        if(maze[i]=='G')g=i;
        for(int j = 0; j < n; j++) {
            if(maze[i]!='*' && maze[j]!='*' &&
                    (abs(i-j)==w || abs(i-j)==1)) {
                wf[i][j] = wf[j][i] = 1;
                wfl[i][j] = j;
                wfl[j][i] = i;
            }
        }
    }
    for(int k = 0; k < n; k++) {
        for(int i = 0; i < n; i++) {
            for(int j = 0; j < n; j++) {
                if(wf[i][k]+wf[k][j]<wf[i][j]) {
                    wf[i][j] = wf[i][k]+wf[k][j];
                    wfl[i][j] = wfl[i][k];
                }
            }
        }
    }
    int x = wfl[s][g];
    while(x!=g) {
        maze[x]='$';
        x = wfl[x][g];
    }
    for(int i = 0; i < (int)lines.size(); i++) {
        cout << string(maze, w*i, w) << endl;
    }
    return 0;
}

**************************
*S* *$$$$$               *
*$* *$ * $*************  *
*$*$$$*  $$************  *
*$$$ *    $$$$$          *
**************$***********
* $$$$$$$$$$$$$          *
**$***********************
* $$$$$*$$$$$$$$$$$$$$G  *
*  *  $$$ *********** *  *
*    *        ******* *  *
*       *                *
**************************