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");
	}
}