백준 17835 면접보는 승법이네 C++

간단한 해설

 

각 도시들 중에서 가장 가까운 면접장의 거리가 가장 먼 도시를 구하는 문제

 

이런 문제는 반대로 생각하면 된다.

각 면접장들 중에서 거리가 가장 먼 도시를 찾으면 되는데, 각 면접장들을 초기 원소로 두고 다익스트라를 하면 된다.

이때, 도로가 단방향이고, 우리는 반대로 구하므로 u->v를 v->u로 두는 것이 포인트

 

답

#include <iostream>
#include <vector>
#include <queue>
#include <climits>
#include <algorithm>
#define ll long long

using namespace std;
vector<vector<pair<ll,ll>>> graph;
ll n,m,k,u,v,c;
int main(){
	cin.tie(0);
	ios_base::sync_with_stdio(0);
	cin>>n>>m>>k;
	graph.resize(n+1,vector<pair<ll,ll>>());
	for(int i=0;i<m;++i){
		cin>>u>>v>>c;
		graph[v].push_back({c,u});
	}
	for(int i=1;i<=n;++i){
		sort(graph[i].begin(),graph[i].end());
	}
	vector<ll> endPoints(k);
	priority_queue<pair<ll,ll>> q;
	vector<ll> visited(n+1,LLONG_MAX-100001);
	for(int i=0;i<k;++i){
		cin>>endPoints[i];
		q.push({0,endPoints[i]});
		visited[endPoints[i]]=0;
	}
	while(!q.empty()){
		ll crnDis=-q.top().first;
		ll crnPoints=q.top().second;
		q.pop();
		if(crnDis!=visited[crnPoints]){
			continue;
		} 
		for(int i=0;i<graph[crnPoints].size();++i){
			ll nxtDis=graph[crnPoints][i].first+crnDis;
			ll nxtPoints=graph[crnPoints][i].second;
			if(visited[nxtPoints]>nxtDis){
				visited[nxtPoints]=nxtDis;
				q.push({-nxtDis,nxtPoints});
			}
		}
	}
	pair<ll,ll> ans={0,-1};
	for(int i=1;i<=n;++i){
		if(visited[i]==LLONG_MAX-100001) continue;
		if(visited[i]>ans.first){
			ans={visited[i],i};
		}
	}
	cout<<ans.second<<"\n"<<ans.first;

}