백준 Gold 3 파티

파티 (백준 Gold 3)

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

처음에는 플로이드 - 워셜 인줄 알았으나
n이 1000개 들어올 수 있다는 걸 보고
BFS로 풀어야 겠다고 생각하였다

다만 길이 단방향으로 존재하며
각 길의 비용이 다르기에
다익스트라로 풀어야 안전하게 풀 수 있다고 생각하였다

다익스트라를 이용한 풀이 방식?

다익스트라는 여러모로 훌륭한 Greedy 기반의
길찾기 알고리즘이다

현재까지 ‘탐색’한 가장 ‘짧은 거리’의 정점을
기반으로 그 경로를 기반으로 목적지까지의
가장 짧은 거리를 찾는다

구현을 할 때
Priority_queue를 사용하는 편
(우선순위 큐의 ‘최소힙’ 구현 방식을 통해
가장 ‘짧은 거리’를 위에 놓은 상황으로 탐색)

결과

제출 코드

#include<iostream>
#include<vector>
#include<queue>
#include<unordered_map>
#include<limits.h>

using namespace std;

typedef pair<int, int> pii;

int n,m,x;

struct infos
{
	int now;
	int nowCost;
};

struct Compare
{
	bool operator()(const infos& a, const infos& b) const
	{
		return a.nowCost > b.nowCost;
	}
};

int bfs(unordered_map<int, vector<pii>>& roads, int start, int to)
{
	priority_queue<infos,vector<infos>,Compare> pq;

	pq.push({ start,0 });

	vector<int> saved(n + 1,INT_MAX);
	int ret = 0;

	while (pq.empty() == false)
	{
		int now = pq.top().now;
		int nowCost = pq.top().nowCost;
		pq.pop();

		if (saved[now] < nowCost)
			continue;

		saved[now] = nowCost;

		if (now == to)
		{
			return nowCost;
		}

		for (auto p : roads[now])
		{
			pq.push({ p.first,nowCost + p.second });
		}
	}

	return -1; // 모든 거리가 연결되어 있다 가정하였기에 사실상 의미 없음
}

int main()
{
	cin >> n >> m >> x;

	unordered_map<int, vector<pii>> roads;

	for (int i = 0; i < m; i++)
	{
		int start, to, cost;
		cin >> start >> to >> cost;

		roads[start].push_back({ to,cost });
	}

	int maxV = 0;

	for (int i = 1; i <= n; i++)
	{
		int v1 = bfs(roads, i, x);
		int v2 = bfs(roads, x, i);
		if (v1 + v2 > maxV)
			maxV = v1 + v2;
	}

	cout << maxV;

	return 0;
}