글 읽기 - 플로이드 와샬알고리즘으로 풀면은..

pch1623 3년 전 0

플로이드 와샬알고리즘으로 풀엇는데요 코드가 플로이드가 더 간편하더라구요

근데 이문제를 사람들이 다익스트라로 많이 푸는 이유가 따로있나요 ??

#include<iostream>
#include<algorithm>

using namespace std;
typedef long long ll;

ll INF = 987654321;
ll arr[805][805];
int main() {
	cin.tie(NULL);
	ios::sync_with_stdio(false);

	
	int N, M;
	cin >> N >> M;

	//배열 초기화
	for (int i = 1; i <= N; i++) {
		for (int j = 1; j <= N; j++){
			if (i == j)arr[i][j] = 0;
			else arr[i][j] = INF;
		}
	}

	//간선데이터 입력
	for (int i = 0; i < M; i++) {
		int a, b, c;
		cin >> a >> b >> c;
		arr[a][b] = c;
		arr[b][a] = c;
	}

	//플루이드 와샬
	for (int k = 1; k <= N; k++) {
		for (int i = 1; i <= N; i++) {
			for (int j = 1; j <= N; j++) {
				if (i == j)continue;
				arr[i][j] = min(arr[i][j], arr[i][k] + arr[k][j]);
			}
		}
	}




	int a, b;

	cin >> a >> b;
	ll result = min(arr[1][a] + arr[a][b] + arr[b][N], arr[1][b] + arr[b][a] + arr[a][N]);
	if (result >= INF)cout << -1;
	else cout << result;


			
}

djm03178 3년 전 6

이유라고 하자면,

다익스트라만 알고 플로이드는 모르는 사람이 많습니다.
다익스트라가 더 효율적입니다. 다익스트라는 N이 수십만이어도 풀 수 있지만, 플로이드는 그렇지 않습니다.
플로이드의 시간 복잡도인 O(N^3)을 N=800일 때 수행하면 통과되지 못할 것으로 생각하여 시도조차 하지 않는 사람도 많습니다. 실제로도 상수가 조금만 커도 800^3은 1초 내에 돌지 못하지만, 플로이드의 상수가 워낙 작아서 잘 통과될 뿐입니다.

pch1623 3년 전 0

좋은답변 감사합니다.

댓글을 작성하려면 로그인해야 합니다.

문제

문제

출처

ICPC

플로이드 와샬알고리즘으로 풀면은..

pch1623 3년 전 0

djm03178 3년 전 6

pch1623 3년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말