[BOJ] 1238 파티 C++

개요

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

1238번: 파티

골드3 난이도 문제!

풀이

학생들이 파티가 열리는 마을에 갔다가 자신의 마을로 돌아와야한다.

이러한 학생들중 가장 오래 걸리는 학생의 소요시간을 출력하면 된다.

우선순위 큐를 이용한 다익스트라를 사용했다.(O(ElogE))

Dijkstra 함수의 매개변수로 출발지와 목적지를 받았다.

목적지에 도착했을 경우, 파티 장소인지 체크 후 파티장소일 경우 집을 목적지로 Dijkstra를 재귀호출했다.

이후 리턴 값을 받아 합이 가장 큰(소요시간이 가장 긴) 결과를 출력하면 끝!

코드

#include<iostream>
#include<algorithm>
#include<vector>
#include<queue>
using namespace std;
constexpr int LIMIT = 1002;
constexpr int MAX = 2123456789;
struct Info{
	int node;
	int cost;
};
struct cmp{
	bool operator()(Info &l, Info &r){
		return l.cost>r.cost;
	}
};

vector<Info> graph[LIMIT];
int N, M, X;
int ans;


int Dijkstra(int start, int end)
{
	priority_queue<Info, vector<Info>, cmp> pq;
	int distance[N+1];
	bool visited[N+1]{};
	for(auto &d : distance)
		d = MAX;
	visited[start] = true;

	pq.push({start, 0});

	while(!pq.empty())
	{
		auto [cur, sum] = pq.top();
		visited[cur] = true;
		pq.pop();

		if(cur == end)
		{
			if(end == X && start != end)
			{
				sum += Dijkstra(end, start);
				if(ans < sum) ans = sum;
			} 
			return sum;
		}

		for(int i=0; i<graph[cur].size(); i++)
		{
			Info next = graph[cur][i];
			if(visited[next.node]) continue;
			int nSum = sum + next.cost;
			if(distance[next.node] < nSum) continue;
			pq.push({next.node, nSum});
		}
	}

}

int main()
{
	cin.tie(0)->sync_with_stdio(0);

	cin >> N >> M >> X;
	int s,e,t;
	for(int i=0; i<M; i++)
	{
		cin >> s >> e >> t;
		graph[s].push_back({e,t});
	}

	for(int i=1; i<=N; i++)
	{
		int cost = Dijkstra(i,X);
		if(ans < cost) ans = cost;
	}

	cout << ans;
}