백준 11404번 플로이드

 

 

 

문제 보러가기 : https://www.acmicpc.net/problem/11404

 

 

11404번: 플로이드

 

 

이번 문제는 플로이드-워샬(Floyd-Warshall) 문제였습니다.

 

플로이드-워샬 알고리즘은 모든 정점 간의 최단 경로를 구하는 알고리즘입니다. 😊

 

 

 

 

《문제 풀이》

 

1. i == j 이면 0, 아니라면 무한대로 초기화 

2. 버스의 정보 입력 (시작 도시 a, 도착 도시 b, 한 번 타는데 필요한 비용 c)

3. 플로이드 워샬 알고리즘

     --> 정점을 거쳐가는 것이 더 빠르다면 graph[from][to] = graph[from][via] + graph[via][to] 로 갱신 

4. i -> j 로 가는 경로가 없다면 해당 값 대신에 "0" 출력 

 

 

 

 

《C++ 코드》

 

#include <bits/stdc++.h>
#define INF 987654321

using namespace std;

int n, m;
int graph[101][101];

// i->i 로 가는 경로는 0  
void initial() {
	for(int i=1; i<=n; i++)
		for(int j=1; j<=n; j++)
			graph[i][j] = i == j ? 0 : INF;
}

void floyd() {
	// 정점을 거쳐가는 것이 더 빠르다면 갱신  
	for(int via=1; via<=n; via++) 
		for(int from=1; from<=n; from++) 
			for(int to=1; to<=n; to++) 
				graph[from][to] = min(graph[from][to], graph[from][via] + graph[via][to]);
}

int main(){
	ios::sync_with_stdio(0);
	cin.tie(0);
	
	cin>>n>>m;
	initial();
	
	for(int i=0; i<m; i++) {
		int a, b, c;
		cin>>a>>b>>c;
		
		graph[a][b] = min(graph[a][b], c);
	}
	
	floyd(); // 플로이드-워샬  
	
	for(int i=1; i<=n; i++) {
		for(int j=1; j<=n; j++) {
			// i->j 경로가 없으면  
			if(graph[i][j] == INF)
				cout<<"0"<<" ";
			else
				cout<<graph[i][j]<<" ";
		}
		cout<<"\n";
	}
	return 0;
}

 

 

개발 환경: Dev-C++

 

 

 

baekjoon - 정답 화면