uos-machine-learning
11404 - 플로이드 본문
플로이드는 다익스트라로도 풀 수 있다.
#include <string.h>
#include <iostream>
#include <queue>
#include <vector>
using namespace std;
// dist[i][j] -> i에서 j로 가는 최단 경로
int dist[101][101];
bool visited[101];
int N, M;
// 인접리스트 adj[i] = {(v1, x1), (v2, x2)}
vector<pair<int, int>> adj[101];
void dijkstra(int root) {
dist[root][root] = 0;
priority_queue<pair<int, int>> q;
q.push({ 0, root });
// visited 배열 초기화
memset(visited, 0, sizeof(visited));
while (!q.empty()) {
int now = q.top().second;
q.pop();
if (visited[now]) continue;
visited[now] = true;
for (auto p : adj[now]) {
int next = p.first;
int w = p.second;
if (dist[root][now] + w < dist[root][next]) {
dist[root][next] = dist[root][now] + w;
q.push({ -dist[root][next], next });
}
}
}
}
int main()
{
cin >> N;
cin >> M;
while (M--) {
int u, v, x;
cin >> u >> v >> x;
adj[u].push_back(make_pair(v, x));
}
for (int i = 1; i <= N; i++) {
for (int j = 1; j <= N; j++) {
dist[i][j] = 0x7ffffff;
}
dijkstra(i);
}
for (int i = 1; i <= N; i++) {
for (int j = 1; j <= N; j++) {
//inf이면 간선이 없다는 뜻
if (dist[i][j] == 0x7ffffff) {
dist[i][j] = 0;
}
printf("%d ", dist[i][j]);
}printf("\n");
}
}
'알고리즘 > 문제풀이' 카테고리의 다른 글
1865 - 웜홀 (0) | 2019.05.14 |
---|---|
11657 - 타임머신 (0) | 2019.05.14 |
11403 - 경로 찾기 (0) | 2019.05.11 |
1956 - 운동 (0) | 2019.05.11 |
11779 - 최소비용 구하기 (0) | 2019.05.11 |
Comments