[백준/BOJ] 백준 17835번 : 면접보는 승범이네

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

17835번: 면접보는 승범이네

도로를 거꾸로 연결하여 그래프를 만들고 각각의 면접장에서 각각의 도시로 가는 최단 경로를 구해서 어떤 면접장에서 왔을 때 최적인 도시로의 최단경로가 정해졌을 때 가장 긴 거리의 도시를 구한다.

 

코드

#include <iostream>
#include <algorithm>
#include <vector>
#include <queue>
#include <limits>
using namespace std;

int n, m, k;
vector<pair<int, int>> adj[100005];
vector<int> start;
int result_area = 0;
long long result_dist = 0;

void Solve()
{
	vector<long long> dist(100005, numeric_limits<long long>::max());
	priority_queue<pair<long long, int>> pq;

	for (int i = 0; i < start.size(); i++)
	{
		dist[start[i]] = 0;
		pq.push(make_pair(-0, start[i]));
	}

	while (!pq.empty())
	{
		int here = pq.top().second;
		long long here_cost = -pq.top().first;
		pq.pop();

		//here도시로 가는 더 빠른 경우가 있을때
		if (dist[here] < here_cost)
			continue;

		for (int i = 0; i < adj[here].size(); i++)
		{
			int there = adj[here][i].second;
			long long there_cost = here_cost + (long long)adj[here][i].first;

			if (dist[there] > there_cost)
			{
				dist[there] = there_cost;
				pq.push(make_pair(-there_cost, there));
			}
		}
	}

	for (int i = 1; i <= n; i++)
	{
		if (result_dist < dist[i])
		{
			result_dist = dist[i];
			result_area = i;
		}
	}
}

int main()
{
	cin.tie(NULL);
	ios_base::sync_with_stdio(false);

	cin >> n >> m >> k;

	for (int i = 0; i < m; i++)
	{
		int u, v, c;
		cin >> u >> v >> c;

		adj[v].push_back(make_pair(c, u)); //거꾸로 먼접장에서 각 위치로 가는것을 위해 간선을 거꾸로 연결
	}

	for (int i = 0; i < k; i++)
	{
		int input;
		cin >> input;

		start.push_back(input);
	}

	Solve();

	cout << result_area << "\n";
	cout << result_dist << "\n";

	return 0;
}