[伯俊]1404フロイド
スタンダード11404フロイド https://www.acmicpc.net/problem/11404
#include <iostream>
#include <algorithm>
using namespace std;
typedef long long ll;
const int MAX_V = 100;
const ll INF = 987654321;
//정점의 개수
int V;
//그래프의 인접 행렬 표현
//adj[u][v] = u에서 v로 가는 간선의 가중치
ll adj[MAX_V][MAX_V];
//플로이드-와샬 알고리즘
void floyd() {
for (int i = 0; i < V; ++i)
adj[i][i] = 0LL;
//i지점 -> j지점으로 이동할 때 거쳐가는 지점 K
for (int k = 0; k < V; ++k)
for (int i = 0; i < V; ++i)
for (int j = 0; j < V; ++j)
adj[i][j] = min(adj[i][j], adj[i][k] + adj[k][j]);
}
int main() {
ios_base::sync_with_stdio(false);
cin.tie(NULL); cout.tie(NULL);
//adj 초기화
for (int i = 0; i < MAX_V; ++i)
for (int j = 0; j < MAX_V; ++j)
adj[i][j] = INF;
//버스의 개수
int E;
cin >> V >> E;
for (int i = 0; i < E; ++i) {
int a, b;
ll c;
cin >> a >> b >> c;
adj[a-1][b-1] = min(adj[a-1][b-1], c);
}
floyd();
for (int i = 0; i < V; ++i) {
for (int j = 0; j < V; ++j) {
if (adj[i][j] < INF) cout << adj[i][j] << " ";
else cout << "0 ";
}
cout << "\n";
}
return 0;
}
Reference
この問題について([伯俊]1404フロイド), 我々は、より多くの情報をここで見つけました https://velog.io/@sunjoo9912/백준-11404-플로이드テキストは自由に共有またはコピーできます。ただし、このドキュメントのURLは参考URLとして残しておいてください。
Collection and Share based on the CC Protocol