[백준] 11404-플로이드(C++)

문제링크: https://www.acmicpc.net/problem/11404

11404번: 플로이드

문제 제목처럼 플로이드 와샬 알고리즘 문제이지만.. 다익스트라로 풀었다... (속도차이도 크게 안나요.. 취존...)

 

 

접근방식

 

1. 전형적인 최단거리를 구하는 문제 

 

2. 다만 모든 좌표에 한해서 최단거리를 구해야하기 때문에 플로이드 와샬문제지만 

쿨하게 다익스트라로 모든 좌표에 대한 최단 거리를 구하고 출력해주었다. 

 

 

문제풀이 

 

1. 전형적인 다익스트라로 구현

 

2. 모든 점에서 다익스트라 호출

주의할 점은 연결이 불가한 경우엔 0을 출력하는것

 

#include <iostream>
#include <vector>
#include <queue>
#include <cstring>
using namespace std;

int n, m;
vector <pair<int, int>> vec[101];
int dist[101];

void dijkstra(int num) {
	priority_queue <pair<int, int>> que;
	que.push(make_pair(0, num));
	dist[num] = 0;

	while (!que.empty()) {
		int cost = que.top().first * -1;
		int cur = que.top().second;
		que.pop();

		for (int i = 0; i < vec[cur].size(); i++) {
			int before_v = dist[vec[cur][i].first];
			int current_v = dist[cur] + vec[cur][i].second;

			if (current_v < before_v) {
				dist[vec[cur][i].first] = current_v;
				que.push(make_pair(current_v*-1, vec[cur][i].first));
			}

		}


	}

}

int main() {
	ios_base::sync_with_stdio(0);
	cin.tie(0), cout.tie(0);

	cin >> n >> m;
	int from, to, cost;
	for (int i = 0; i < m; i++) {
		cin >> from >> to >> cost;
		vec[from].push_back(make_pair(to, cost));
	}
	
	for (int i = 1; i <= n; i++) { // 매 줄마다 반복할거

		for (int j = 1; j <= n; j++)
			dist[j] = 2000000000;

		dijkstra(i);

		for (int j = 1; j <= n; j++) {
			if (dist[j] == 2000000000)
				printf("0 ");
			else
				printf("%d ", dist[j]);
		}
		printf("\n");
	}

	return 0;
}