[백준 1238] 파티

정렬 시, 1번 사람부터 N번 사람까지 해줘야 한다는 것을...

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

1238번: 파티

#include <cstdio>
#include <queue>
#include <list>
#include <algorithm>
int N, M, X;
int sum[1000 + 2];

struct _st
{
	int n;
	int t;
}; 
std::list<_st> L[1000 + 2];

struct COMP
{
	bool operator()(const _st &a, const _st &b) {
		return a.t > b.t;
	}
};
std::priority_queue<_st, std::vector<_st>, COMP> PQ;
int go[1000 + 2];
int come[1000 + 2];


void input()
{
	scanf("%d %d %d", &N, &M, &X);
	for (int i = 0; i < M; i++) {
		int u = 0, v = 0, t = 0;
		scanf("%d %d %d", &u, &v, &t);
		L[u].push_back({ v, t });	// 단방향 
	}
}

void BFS(int start)
{
	//init
	PQ = {};
	for (int i = 1; i <= N; i++) go[i] = 0x7fffffff;

	PQ.push({ start, 0 });
	go[start] = 0;

	while (!PQ.empty()) {
		_st data = PQ.top();
		PQ.pop();

		if (data.n == X) {
			sum[start] = data.t;
			return;
		}

		for (_st next : L[data.n]) {
			if (go[next.n] <= go[data.n] + next.t) continue;
			PQ.push({ next.n, go[data.n] + next.t });
			go[next.n] = go[data.n] + next.t;
		}
	}
}


void to_x()
{
	for (int s = 1; s <= N; s++) {
		BFS(s);
	}
}


void from_x(int start)
{
	//init
	PQ = {};
	for (int i = 1; i <= N; i++) come[i] = 0x7fffffff;

	PQ.push({start, 0});
	come[start] = 0;

	while (!PQ.empty()) {
		_st data = PQ.top();
		PQ.pop();

		for (_st next : L[data.n]) {
			if (come[next.n] <= come[data.n] + next.t) continue;
			PQ.push({ next.n, come[data.n] + next.t });
			come[next.n] = come[data.n] + next.t;
		}
	}
}


void output()
{
	for (int i = 1; i <= N; i++) {
		sum[i] += come[i];
	}
	std::sort(sum + 1, sum + N + 1);
	printf("%d\n", sum[N]);
}


int main()
{
	input();
	to_x();
	from_x(X);
	output();
	return 0;
}

1. 특정 노드까지 가는 cost가 다르므로 우선순위 큐를 사용한다. 

2. 1부터 N까지의 학생들이 X라는 목적지에 가기위한 최단시간을 구하기 위해 BFS를 N번 돌려준다. 

3. 1부터 N까지의 학생들이 X라는 출발지에서 각자의 집으로 돌아오기 위한 최단 시간을 구하기 위해 from_X 함수를 1번 돌려준다. 

4. 2와 3번에서 구한 결과를 더해 sum이라는 배열에 저장하고, 오름차순으로 정렬 후 가장 끝 값을 출력한다. 

그래야 오고 가는데 가장 많은 시간을 소비한 학생을 구할 수 있다.