백준 알고리즘 풀이 11404번 - 플로이드

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

11404번: 플로이드

 

- 플로이드 와샬 문제

 

- 알고리즘 -

1. 플로이드 와샬 알고리즘을 통해 모든 도시로 가는데 필요한 비용의 최솟값을 구한다. 

(플로이드 알고리즘 설명 : )

-시간 복잡도-

floyd warshall 알고리즘이 기본적으로 n^3.  

- 예외 조건 -

1. 같은 경로의 비용이 들어올 수 있다. 이때 가장 최소의 경로를 넣어야하므로, algorithm 헤더의 min 함수를 사용하기로 하자.

 

-소스 코드-

#include <iostream>
#include <algorithm>
#define MAX 100001

using namespace std;

int map[101][101];
int n,m;//n이 시작도시 , m이 도착도시

void fw()
{
	for(int via=1;via<=n;via++){
		for(int from=1;from<=n;from++){
			if(map[from][via]==0) continue;
			for(int to=1;to<=n;to++){
				if(map[via][to]==0 || from==to) continue;
				if(map[from][to]==0 || map[from][to]>map[from][via]+map[via][to]){
					map[from][to]=map[from][via]+map[via][to];
				}
			}
		}
	}	
}

int main() 
{
	cin>>n>>m;
	int from,to,cost;
	for(int i=1;i<=m;i++)
	{
		cin>>from>>to>>cost;
		if(!map[from][to])	map[from][to]=cost;
		else	map[from][to]=min(cost,map[from][to]);	
	}
	fw();
	for(int i=1;i<=n;i++)
	{
		for(int j=1;j<=n;j++){
			cout<<map[i][j]<<" ";
		}
		cout<<endl;
	}
}

 

 

틀린 내용이나 지적 언제나 환영입니다.

도움이 되었다면 하트 한번씩 눌러주세요:)