[C++/백준] 11404 플로이드

11404번: 플로이드

 

 

[문제 요약]

비용이 측정된 간선이 있고, 가장 작은 비용으로 갈 수 있는 값을 구해라. 

 

[아이디어 구현 과정]

사실, 플로이드 워샬을 오랜만에 풀어보고 싶어서 제목만 보고 선택하게 되었는데, 보다보니까 플로이드는 기억이 안나고 Dijkstra만 생각이 났다... 

시간 복잡도를 계산 해보니 다익스트라를 사용한다고 시간 초과에 걸리지 않았고, 그냥 다익스트라를 사용하기로 했다 ㅎ

 

시간복잡도는 최대 100개 도시, 100,000개 버스 

 

=> 1. 한개의 도시에서 다른 도시까지 모든 최소 비용을 찾는 (Dijkstra) 99

2. 1번 과정을 100번 반복 -> 100 * 100,000-> 10,000,000

 

 

[전체 코드 - Dijkstra]

#include<iostream>
#include<vector>
#include<queue>
#include<algorithm>

using namespace std;

int N,M;

long long cost[102][102];
typedef pair<int, int> pii;

void Dijkstra(int n, vector<vector<pii>>&b_stop) {
	long long  visited[102];
	priority_queue<pii> pq;

	fill(visited, visited + 102, 2e9);

	int start = n;

	pq.push({ 0, n });

	// 다익스트라
	while (!pq.empty()) {
		//비용 : 양의 값으로 꺼내옴
		int v = -pq.top().first;
		//현재 도시
		int b = pq.top().second;
		pq.pop();

		if (visited[b] !=2e9) continue;
		
		visited[b] = v;

		for (int i = 0; i < b_stop[b].size(); i++) {
			
			//갈 수 있는 도시
			int l = b_stop[b][i].second;
			//지금까지의 비용에 더한다
			int c = visited[b] + b_stop[b][i].first;
			
			if (visited[l] != 2e9) continue;
			
			pq.push({ -c, l });
		}
	}
	
	//다익스트라 한 내용을 cost에 저장
	for (int i = 1; i <= N; i++) {
		cost[n][i] = visited[i];
		if (visited[i] == 2e9)cost[n][i] = 0;
	}
}


int main() {
	ios::sync_with_stdio(false);
	cin >> N;
	cin >> M;

	vector<vector<pii>> b_stop(N+1);
	
	for (int j = 0; j < M; j++) {
		int a, b, c;
		cin >> a >> b >> c;
		b_stop[a].push_back({ c, b });
	}

	for (int i = 1; i <= N; i++) {
		Dijkstra(i,b_stop);
	}

	for (int i = 1; i <= N; i++) {
		for (int j = 1; j <= N; j++) {
			cout <<cost[i][j]<<' ';
		}
		cout << '\n';
	}

}

 

[전체 코드 - 플로이드 워셜]

#include<iostream>
#include<algorithm>

using namespace std;

int cost[102][102];
long long dist[102][102];
int N, M;

int main() {

	fill(&cost[0][0], &cost[0][0] + 102 * 102, 2e9);
	cin >> N;
	cin >> M;

	for (int i = 0; i < M; i++) {
		int a, b, c;
		cin >> a >> b >> c;
		//a에서 b까지 가는 비용 c를 넣음
		cost[a][b] = min(c,cost[a][b]);
	}

	for (int i = 1; i <= N; i++) {
		for (int j = 1; j <= N; j++) {
			dist[i][j] = cost[i][j];
			if (i == j) dist[i][j] = 0;
		}
	}

	//플로이드

	for (int k = 1; k <= N; k++) {
		for (int i = 1; i <= N; i++) {
			for (int j = 1; j <= N; j++) {
				dist[i][j] = min(dist[i][j], dist[i][k] + dist[k][j]);
			}
		}
	}

	for (int i = 1; i <= N; i++) {
		for (int j = 1; j <= N; j++) {
			if (dist[i][j] >= 2e9) dist[i][j] = 0;
			cout << dist[i][j] << ' ';
		}
		cout << '\n';
	}


	
	return 0;
}

 

[후기]

다익스트라도 오랜만에 하니까 처음엔 이상한 방법으로 풀었었다 ㅎㅎ.. 

이래서 자주자주 해야하는데 ㅜㅠ 주에 알고리즘 스터디 문제밖에 안풀게 됨...