[백준 17835] 면접보는 승범이네 (C++)

문제 링크: https://www.acmicpc.net/problem/17835

17835번: 면접보는 승범이네

1. 주의할 점

- 모든 변수를 Long Long으로 받아들인다

 

2. 구현

- 면접장으로 가는것이 아닌 면접장에서 출발하도록 그래프의 방향을 바꿔서 넣는다

- 면접장을 우선순위큐에 넣고 다익스트라 알고리즘을 통해 각 도시까지의 거리를 구한다

- For문을 수행하며 1부터 Node 번호까지 비교하여 Maxi, Result을 갱신한다

 

#define MAX 10000000000000
#include <iostream>
#include <queue>
#include <vector>
#include <algorithm>
using namespace std;
struct info {
	long long idx, val;
};
struct cmp {
	bool operator()(info &a, info &b) {
		return a.val > b.val;
	}
};
info tmp;
vector<info> v[100001];
long long dist[100001], maxi = 0, node, edge, k, s, e, val, result;

int main() {
	ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
	cin >> node >> edge >> k;
	//초기화
	for (int i = 1; i <= node; i++)
		dist[i] = MAX;
	for (int i = 0; i < edge; i++) {
		cin >> s >> e >> val;
		tmp.idx = s;
		tmp.val = val;
		v[e].push_back(tmp);
	}
	priority_queue<info, vector<info>, cmp> pq;
	for (int i = 0; i < k; i++) {
		cin >> s;
		tmp.idx = s;
		tmp.val = 0;
		pq.push(tmp);
		dist[s] = 0;
	}
	while (!pq.empty()) {
		long long cidx = pq.top().idx;
		long long cv = pq.top().val;
		pq.pop();
		if (dist[cidx] < cv) continue;
		for (int i = 0; i < v[cidx].size(); i++) {
			long long next = v[cidx][i].idx;
			long long nv = v[cidx][i].val;
			if (dist[next] > cv + nv) {
				dist[next] = cv + nv;
				tmp.idx = next;
				tmp.val = cv + nv;
				pq.push(tmp);
			}
		}
	}
	for (int i = 1; i <= node; i++) {
		if (dist[i] > maxi) {
			maxi = dist[i];
			result = i;
		}
	}
	cout << result << '\n' << maxi;
	system("pause");
	return 0;
}