BOJ (C/C++) 11404번: 플로이드

https://www.acmicpc.net/problem/11404

11404번: 플로이드

---

풀이

문제 이름에서부터 알 수 있듯이 플로이드-와샬을 쓰는 문제다.
문제의 "시작 도시와 도착 도시를 연결하는 노선은 하나가 아닐 수 있다." 는 문구가 있으므로 값을 입력 받는 부분에서도 최솟값을 입력 받아야 한다.다익스트라로도 풀어봤지만 코드 길이와 시간 면에서 플로이드-와샬의 성능이 더 좋다.

---

코드 1 - 플로이드

#include <stdio.h>
#include <algorithm>
#include <limits.h>
using namespace std;

#define INF 100000000
int Min(int a, int b) { if (a < b) return a; return b; }
int main() {
	int N, M, a, b, c;
	int D[101][101];

	// init
	fill(D[0], D[101], INF);
	for (int i = 1; i <= 100; i++) D[i][i] = 0;

	// input
	scanf("%d %d", &N, &M);
	for (int i = 0; i < M; i++) {
		scanf("%d %d %d", &a, &b, &c);
		D[a][b] = Min(c, D[a][b]);
	}

	// floyd - warshall
	for (int k = 1; k <= N; k++) {
		for (int i = 1; i <= N; i++) {
			for (int j = 1; j <= N; j++) {
				D[i][j] = Min(D[i][j], D[i][k] + D[k][j]);
			}
		}
	}

	// print
	for (int i = 1; i <= N; i++) {
		for (int j = 1; j <= N; j++) {
			if (D[i][j] == INF) D[i][j] = 0;
			printf("%d ", D[i][j]);
		}
		printf("\n");
	}
	return 0;
}

---

코드 2 - 다익스트라

#include <stdio.h>
#include <vector>
#include <queue>
#include <algorithm>
using namespace std;

#define MAX 100000000

vector <pair<int, int>> V[101];
int Distance[101];

 void Dijkstra(int start, int N) {
	priority_queue <pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>>> pq;
	int now, dis, next;
	int D[101];

	fill(D, D + N, MAX);
	D[start] = 0;
	pq.push({ 0,start });

	while (!pq.empty()) {
		now = pq.top().second, dis = pq.top().first;
		pq.pop();
		if (D[now] < dis) continue;

		for (int i = 0; i < V[now].size(); i++) {
			next = V[now][i].first, dis = V[now][i].second;
			if (D[next] > D[now] + dis) {
				D[next] = D[now] + dis;
				pq.push({ D[next],next });
			}
		}
	}
    
    	//print
	for (int i = 1; i < N; i++) {
		if (D[i] == MAX) D[i] = 0;
		printf("%d ", D[i]);
	}
	printf("\n");
}

int main() {
	int N, M;
	int a, b, c;
	scanf("%d %d", &N, &M);
	for (int i = 0; i < M; i++) {
		scanf("%d %d %d", &a, &b, &c);
		V[a].push_back({ b,c });
	}
	for (int i = 1; i <= N; i++) Dijkstra(i, N+1);
	return 0;
}