85709


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

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

[code]

    #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;
    }
    
[/code]

入力：

[code]

    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
    
[/code]

出力：

[code]

    0 6
    
[/code]

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


CC BY-SA 4.0
2022-01-07T12:16:58.347
85550
2022-01-18T12:09:46.383
2022-01-18T12:08:10.410
50767
50767
question
c++ アルゴリズム
ワーシャルフロイド法を使った経路復元のコードをまとめてみましたが結果の出力が思うようにいきません。


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

[code]

    #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;
    }
    
[/code]

入力：

[code]

    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
    
[/code]

出力：

[code]

    0 2 3 4 6
    
[/code]

↑

[code]

    0 2 3 5 4 6
    
[/code]

にならない。


CC BY-SA 4.0
2022-01-11T09:02:53.013
85619
2022-01-11T09:34:03.430
2022-01-11T09:34:03.430
50767
50767
85550
answer


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

[code]

    #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;
    }
    
[/code]

入力：

[code]

    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
    
[/code]

出力：

[code]

    0 2 3 5 4 6
    
[/code]


CC BY-SA 4.0
2022-01-15T08:02:55.757
85709
2022-01-18T12:09:46.383
2022-01-18T12:09:46.383
3060
50767
85550
answer