Skip to main content
タグを編集
リンク
yn95ny
  • 298
  • 3
  • 8
本文に 1 文字追加
ソース リンク
yn95ny
  • 298
  • 3
  • 8
0 6
06
0 6
本文に 1 文字追加
ソース リンク
yn95ny
  • 298
  • 3
  • 8
#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 << ";nagative;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;
}
#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 << ";nagative_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;
}
#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;
}
本文に 77 文字追加
ソース リンク
yn95ny
  • 298
  • 3
  • 8
読み込んでいます
本文に 3 文字追加; タイトルを編集
ソース リンク
yn95ny
  • 298
  • 3
  • 8
読み込んでいます
本文に 26 文字追加
ソース リンク
supa
  • 5,399
  • 4
  • 18
  • 41
読み込んでいます
ソース リンク
yn95ny
  • 298
  • 3
  • 8
読み込んでいます