1238번: 파티

문제 설명

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

1238번: 파티

[문제]

 N개의 숫자로 구분된 각각의 마을에 한 명의 학생이 살고 있다.

 어느 날 이 N명의 학생이 X (1 ≤ X ≤ N)번 마을에 모여서 파티를 벌이기로 했다. 이 마을 사이에는 총 M개의 단방향 도로들이 있고 i번째 길을 지나는데 Ti(1 ≤ Ti ≤ 100)의 시간을 소비한다.

 각각의 학생들은 파티에 참석하기 위해 걸어가서 다시 그들의 마을로 돌아와야 한다. 하지만 이 학생들은 워낙 게을러서 최단 시간에 오고 가기를 원한다.

 이 도로들은 단방향이기 때문에 아마 그들이 오고 가는 길이 다를지도 모른다. N명의 학생들 중 오고 가는데 가장 많은 시간을 소비하는 학생은 누구일지 구하여라.

 

[입력]

 첫째 줄에 N(1 ≤ N ≤ 1,000), M(1 ≤ M ≤ 10,000), X가 공백으로 구분되어 입력된다. 두 번째 줄부터 M+1번째 줄까지 i번째 도로의 시작점, 끝점, 그리고 이 도로를 지나는데 필요한 소요시간 Ti가 들어온다. 시작점과 끝점이 같은 도로는 없으며, 시작점과 한 도시 A에서 다른 도시 B로 가는 도로의 개수는 최대 1개이다.

 모든 학생들은 집에서 X에 갈수 있고, X에서 집으로 돌아올 수 있는 데이터만 입력으로 주어진다.

 

[출력]

 첫 번째 줄에 N명의 학생들 중 오고 가는데 가장 오래 걸리는 학생의 소요시간을 출력한다.

 

[예제 입력 1]

4 8 2
1 2 4
1 3 2
1 4 7
2 1 1
2 3 5
3 1 2
3 4 4
4 2 3

[예제 출력 1]

10

---

풀이

 해당 문제의 경우 모든 학생들에 대하여 경로를 탐색할 필요가 있다고 판단하여 하나의 점에 대해서 탐색을 진행하는 다익스트라가 아닌 플로이드-와샬 알고리즘을 사용했다.

 알고리즘 자체가 간단하고 직관적이어서 어렵진 않았지만, 최종 시간이 900ms 가량이 나와 이를 좀 더 줄여보고자 사이에 조건문을 넣었다. 3중 for문 중에서 중간 노드와 시작 노드가 결정된 상태에서 해당 비용이 INF인 경우 세부 반복문을 건너뛰게 작성했는데, 시간이 절반정도로 크게 줄어들었다.

 

#include <iostream>
#include <algorithm>

using namespace std;

#define INF 1000001

int dist[1001][1001];

int main() {
	int N, M, X;
	int p1, p2, cost;
	int answer = -1;

	cin >> N >> M >> X;

	for (int i = 1; i <= N; i++) {//그래프 초기화
		for (int j = 1; j <= N; j++) {
			dist[i][j] = INF;
		}
		dist[i][i] = 0;
	}

	for (int i = 0; i < M; i++) {//비용 입력
		cin >> p1 >> p2 >> cost;
		dist[p1][p2] = cost;
	}

	for (int k = 1; k <= N; k++) //플로이드-와샬 알고리즘 사용
		for (int i = 1; i <= N; i++)
			if(dist[i][k]!=INF) //조건문 추가 -> 길이 없는 경우는 탐색 X
				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++) //최대값 탐색
		answer = max(answer, dist[i][X] + dist[X][i]);

	cout << answer;

	return 0;
}

---

결과

 위에는 조건문을 추가한 경우, 아래는 조건문 없이 제출한 경우이다.