0

コードを書いてみましたが出力が意図した通りになりません。

コメントのグラフを以下のコードの形式で入力して出力を各ノードにおけるコストの合計の羅列にしたいのですが、まだ理解不足です。

解る方よろしくお願します。

#include <iostream>
#include <vector>
using namespace std;
const long long MAX_V = 50;
const long long INF = 1e9;
long long V;
long long d[MAX_V][MAX_V];
void input() {
    cin >> V;
    for (int i = 0; i < V; i++) {
        for (int j = 0; j < V; j++) {
            cin >> d[i][j];
        }
    } 
}
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]);
            }
        }
    }
}
void output(){
    for (int i = 0; i < V; i++) {
        for (int j = 0; j < V; j++) {
            if (d[i][j] == INF) {
                cout << "INF";
            }
            else if (d[i][j] == -1)break;
            else {
                cout << d[i][j];
            }
        }
    }
}
int main()
{
    input();
    warshall_floyd();
    output();
    return 0;
}

input:
7
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
output:
0000000000000000000000000000000000000000000000000

//vector<vector<long long>> d = { {0,2,5,INF,INF,INF,INF},
//                                  {2,0,4,6,10,INF,INF},
//                                  {5,4,0,2,INF,INF,INF},
//                                  {INF,6,2,0,INF,1,INF},
//                                  {INF,10,INF,INF,0,3,5},
//                                  {INF,INF,INF,1,3,0,9},
//                                  {INF, INF,INF,INF,5,9,0} };
2
  • 1
    コメント側にはINFがありますがinputは0になっていてそもそも入力が一致していないのでは?
    – sayuri
    Commented 2022年1月5日 23:07
  • INFで入力するとプログラムが実行できなかったので、input側ではINFの所も0で入力しています。
    – yn95ny
    Commented 2022年1月6日 0:04

2 件の回答 2

0

入力の0INFに読み替えてください。

void input() {
    cin >> V;
    for (int i = 0; i < V; i++) {
        for (int j = 0; j < V; j++) {
            cin >> d[i][j];
            // 以下の3行をを追加
            if (d[i][j] == 0) {
                d[i][j] = INF;
            }
        }
    } 
}

ついでに、出力が読みにくかったので少し変えました。

void output(){
    for (int i = 0; i < V; i++) {
        for (int j = 0; j < V; j++) {
            if (d[i][j] == INF) {
                cout << "INF";
            } else {
                cout << d[i][j];
            }
            cout << ' ';
        }
        cout << endl;
    }
}

入力:

7
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

出力:

4 2 5 7 11 8 16 
2 4 4 6 10 7 15 
5 4 4 2 6 3 11 
7 6 2 2 4 1 9 
11 10 6 4 6 3 5 
8 7 3 1 3 2 8 
16 15 11 9 5 8 10
0

入力のヒントありがとうございました。無事解決しました。
結局、今回は次のようにコードをまとめました。

#include <iostream>
#include <vector>
using namespace std;
const int MAX_V = 50;
const long long INF = 1e9;
int V;
long long d[MAX_V][MAX_V];
void input() {
    cin >> V;
    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]);
            }
        }
    }
}
void output() {
    for (int i = 0; i < V; i++) {
        for (int j = 0; j < V; j++) {
            if (d[i][j] == INF) {
                cout << "INF";
            }
            else {
                cout << d[i][j];
            }
            cout << ' ';
        }
        cout << endl;
    }
}
int main()
{
    input();
    warshall_floyd();
    output();
    return 0;
}

入力:

7
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 5 7 11 8 16
2 0 4 6 10 7 15
5 4 0 2 6 3 11
7 6 2 0 4 1 9
11 10 6 4 0 3 5
8 7 3 1 3 0 8
16 15 11 9 5 8 0

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

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