개요

백준 1238: 파티

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

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

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

접근방식

1. 맨 처음 생각했던 방법은 그냥 X에서 시작해서 모든 마을까지 걸리는 최단시간을 다익스트라를 이용해 저장 후, 제일 큰값을 *2해주는 방식이였다.

2. 하지만 "틀렸습니다"가 떠서 문제를 다시 살펴보던 중
   문제에서 친절하게

   이 도로들은 단방향이기 때문에 아마 그들이 오고 가는 길이 다를지도 모른다.

   라고 알려줘서
   X에서 각마을로 다익스트라 한번 적용,
   각 마을에서 X로의 다익스트라 알고리즘을 다 적용하는 식으로
   최대값을 구했다.
   

전체 코드

#include<iostream>
#include<vector>
#include<queue>

using namespace std;

int minDist[1001];
int minDistX[1001];
bool visited[1001];
int N, M, X, INF=1'000'000;
vector<vector<pair<int, int>>> v;

priority_queue<pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>>> pq;

void Solution() {
	int Ans = 0;

	fill(minDistX, minDistX + 1001, INF);
	fill(visited, visited + 1001, false);

	minDistX[X] = 0;
	pq.push({ minDistX[X],X });
	//X에서 각 마을로의 다익스트라 알고리즘
	while (!pq.empty()) {
		int curNode = pq.top().second;
		pq.pop();
		while (!pq.empty() && visited[curNode]) {
			curNode = pq.top().second;
			pq.pop();
		}
		//curNode가 방문한 상태인데, pq가 비었다면 위 반복문 탈출함
		if (visited[curNode]) break;

		//방문 처리해주고
		visited[curNode] = true;

		//curnode에 인접한 노드들에 대해 curNode를 거쳐서 가는 거리가 더 짧은지 비교하고 갱신
		for (pair<int, int>& p : v[curNode]) {
			int nextNode = p.first, nextDist = p.second;
			if (minDistX[nextNode] > minDistX[curNode] + nextDist) {
				minDistX[nextNode] = minDistX[curNode] + nextDist;
				pq.push({ minDistX[nextNode],nextNode });
			}
		}
	}

	//각마을에서 x로의 다익스트라 알고리즘
	for (int i = 0; i < N; i++) {
		fill(minDist, minDist + 1001, INF);
		fill(visited, visited + 1001, false);
		minDist[i] = 0;
		pq.push({minDist[i],i});
		while (!pq.empty()) {
			int curNode = pq.top().second;
			pq.pop();
			while (!pq.empty() && visited[curNode]) {
				curNode = pq.top().second;
				pq.pop();
			}

			if (visited[curNode])break;

			visited[curNode] = true;

			for (pair<int, int>& p : v[curNode]) {
				int nextNode = p.first, nextDist = p.second;
				if (minDist[nextNode] > minDist[curNode] + nextDist) {
					minDist[nextNode] = minDist[curNode] + nextDist;
					pq.push({ minDist[nextNode],nextNode });
				}
			}
		}
		//각마을에서 다익스트라가 끝나면 해당 마을에서 X로의 최소값+ X에서 해당 마을로의 최소값 더해준 후, Ans와 비교 후 갱신
		Ans = minDist[X] + minDistX[i] > Ans?minDist[X] + minDistX[i] : Ans;	
	}
	cout << Ans;
}

void Input() {
	int tmpStart, tmpEnd, tmpDist;
	cin >> N >> M >> X;
	X--;
	v.resize(N);
	for (int i = 0; i < M; i++) {
		cin >> tmpStart >> tmpEnd >> tmpDist;
		v[--tmpStart].push_back({ --tmpEnd,tmpDist });
	}

}

int main() {
	ios_base::sync_with_stdio(0);
    cin.tie(0);
	Input();
	Solution();
}

문풀후생

문제를 꼼꼼히 읽고, 단방향일 때 다른 길이 답이 될수 있는지 체크해보자.