백준 1238 파티 풀이

사용언어

Visual studio 2019 C++

생각하기

플로이드 워샬 알고리즘 사용

플로이드 워샬 알고리즘

모든 정점들 사이의 최단경로를 구하는 알고리즘

[1238 풀이]

#include <iostream>
#include <algorithm>
using namespace std;
const int MAX = 1000 + 1;
int road[MAX][MAX];
int N, M, X;

void floyd() {
	for (int i = 1; i <= N; i++) {
		for (int j = 1; j <= N; j++) {
			if (road[j][i] == 0)
				continue;
			for (int k = 1; k <= N; k++) {
				if (road[i][k] == 0 || j == k)
					continue;
				if (road[j][k] == 0 || road[j][k] > road[j][i] + road[i][k]) {
					road[j][k] = road[j][i] + road[i][k];
				}
			}
		}
	}
}

int main() {
	cin >> N >> M >> X;

	for (int i = 0; i < M; i++) {
		int start, end, time;
		cin >> start >> end >> time;
		road[start][end] = time;
	}

	floyd();
	int longtime = 0;;
	for (int i = 1; i <= N; i++) {
		longtime = max(longtime, road[i][X] + road[X][i]);
	}
	cout << longtime << "\n";
}

그냥 궁금한점

ios::sync_with_stdio(false);
cin.tie(NULL);
cout.tie(NULL);

이걸 쓰면 입출력이 빨라져서 시간이 더 조금걸려야 되는거 아닌가..?

꼭 그런건 아닌가…? 11404번문제 플로이드는 88ms -> 24ms 였는데….

이 문제는 없을때는 364ms 있으니까 368ms

왜그러징 궁금!!!하다!!!