0

ワーシャルフロイド法を使って経路復元のプログラムを書いてみましたが結果の出力が思うようにいきません。

vector get_path(int s,int t)のvector ansへのまとめ方が悪いと思うのですがどうでしょうか?

#include <iostream>
#include <vector>
using namespace std;
const int MAX_V = 50;
const long long INF = 1e9;
int V,s,g;
long long d[MAX_V][MAX_V];
long long prever[MAX_V][MAX_V];
void input() {
    cin >> V >> s >> g;
    for (int i = 0; i < V; i++) {
        for (int j = 0; j < V; j++) {
            cin >> d[i][j];
            if (i == j) {
                d[i][j] = 0;
            }
            else if (d[i][j] == 0) {
                d[i][j] = INF;
            }
        }
    }
}

void warshall_floyd(){
    for (int k = 0; k < V; k++) {
        for (int i = 0; i < V; i++) {
            for (int j = 0; j < V; j++) {
                d[i][j] = min(d[i][j], d[i][k] + d[k][j]);
                prever[i][j] = prever[k][j];
            }
        }
    }
    for (int i = 0; i < V; i++) {
        if (d[i][i] < 0) {
            cout << "negative_loop" << endl;
        }
    }
}

vector<int> get_path(int s, int t) {
    vector<int>path;
    for (; t != s; t = prever[s][t]) {
        path.push_back(t);
    }
    path.push_back(s);
    reverse(path.begin(), path.end());
    return path;
}


int main()
{
    input();
    warshall_floyd();
    vector<int>ans = get_path(s,g);
    for (int i = 0; i < ans.size(); i++) {
        if (i != ans.size() - 1)
            printf("%d ", ans[i]);
        else printf("%d\n", ans[i]);
    }
    return 0;
}

入力:

7 0 6
0 2 5 0 0 0 0
2 0 4 6 10 0 0
5 4 0 2 0 0 0
0 6 2 0 0 1 0
0 10 0 0 0 3 5
0 0 0 1 3 0 9
0 0 0 0 5 9 0

出力:

0 6


出力の答えを、0 2 3 5 4 6としたい。

3

2 件の回答 2

0

一部修正しましたがそれでも答えと一致しません。

#include <iostream>
#include <vector>
using namespace std;
const int MAX_V = 50;
const long long INF = 1e9;
int V,s,g;
long long d[MAX_V][MAX_V];
void input() {
    cin >> V >> s >> g;
    for (int i = 0; i < V; i++) {
        for (int j = 0; j < V; j++) {
            cin >> d[i][j];
            if (i == j) {
                d[i][j] = 0;
            }
            else if (d[i][j] == 0) {
                d[i][j] = INF;
            }
        }
    }
}

void warshall_floyd(){
    for (int k = 0; k < V; k++) {
        for (int i = 0; i < V; i++) {
            for (int j = 0; j < V; j++) {
                d[i][j] = min(d[i][j], d[i][k] + d[k][j]);
            }
        }
    }
    for (int i = 0; i < V; i++) {
        if (d[i][i] < 0) {
            cout << "nagative_loop" << endl;
        }
    }
}
void get_path(int s, int g) {
    int cur = s;
    while (cur != g) {
        printf("%d ", cur);

        for (int i = 0; i < V; i++) {
            if (i != cur && d[cur][i] + d[i][g] == d[cur][g]) {
                cur = i;
                break;
            }
        }
    }
    printf("%d\n", g);
}

int main()
{
    input();
    warshall_floyd();
    get_path(s, g);
    return 0;
}

入力:

7 0 6
0 2 5 0 0 0 0
2 0 4 6 10 0 0
5 4 0 2 0 0 0
0 6 2 0 0 1 0
0 10 0 0 0 3 5
0 0 0 1 3 0 9
0 0 0 0 5 9 0

出力:

0 2 3 4 6

   ↑

0 2 3 5 4 6

にならない。

0

入力内容を変えました。出力の結果が予定通りにできました。

#include <iostream>
#include <vector>
using namespace std;
#define rep(i,n)for(int i=0;i<(n);i++)
const int MAX_N = 50;
const long long INF = 1e9;
int d[MAX_N][MAX_N];
int memo[MAX_N][MAX_N];
int V, E, s, g;
void input() {
    cin >> V >> E >> s >> g;
    rep(i, V)rep(j, V)d[i][j] = d[j][i] = INF;
    rep(i, V)rep(j, V)memo[i][j] = memo[j][i] = 0;
    rep(i, V)d[i][i] = 0;
    rep(i, E) {
        int from, to, cost;
        cin >> from >> to >> cost;
        d[from][to] = d[to][from] = cost;
        memo[from][to] = memo[to][from] = cost;
    }
}
void warshall_floyd() {
    rep(k, V)rep(i, V)rep(j, V)
        d[i][j] = min(d[i][j], d[i][k] + d[k][j]);
    printf("%d ", s);
    int cur = s;
    while (cur != g) {
        rep(i, V) {
            if (cur == i)continue;
            else if (d[cur][g] == memo[cur][i] + d[i][g] && memo[cur][i] > 0) {
                cur = i;
                if (cur == g)printf("%d\n", g);
                else printf("%d ", cur);
                break;
            }
        }
    }
}
int main()
{
    input();
    warshall_floyd();
    return 0;
}

入力:

7 10 0 6
0 1 2
0 2 5
1 2 4
1 3 6
1 4 10 
2 3 2
3 5 1 
4 6 5
5 4 3
5 6 9

出力:

0 2 3 5 4 6

この質問に回答するには、ログインする必要があります。

求めていた回答ではありませんか? のタグが付いた他の質問を参照する。