BOJ 17835, 면접보는 승범이네
ProblemSolving ·이 문제는 다익스트라를 이용한 문제입니다.
풀이
면접장을 시작점으로 풀기 위해서 벡터에도 반대로 값을 넣었습니다.
어떻게 풀어야 할지 몰라서 처음에는 k번 다익스트라를 돌려서 시간초과가 났습니다. 미리 시작점을 우선순위 큐에 넣으면 다익스트라 한번에 돌아가더라구요. 근데도 한번 틀렸습니다. 범위때문이지요. int형에서 long long형으로 바꿔주었더니 맞았습니다! 거의 기본 다익스트라문제같습니다.
#include<stdio.h>
#include<iostream>
#include<queue>
#include<functional>
#include<vector>
#include<stack>
using namespace std;
typedef long long ll;
typedef pair <ll, ll> P;
ll n, m, k, a, b,c,Max,Maxi;
ll dist[100001];
vector<vector<P>> v(100001);
priority_queue<P, vector<P>, greater<P>> pq;
void dijk() {
while (!pq.empty()) {
ll cost = pq.top().first;
ll here = pq.top().second;
pq.pop();
if (cost > dist[here]) continue;
for (ll i = 0; i < v[here].size(); i++) {
ll next = v[here][i].first;
ll nextcost = v[here][i].second;
if (dist[next] > dist[here] + nextcost) {
dist[next] = dist[here] + nextcost;
pq.push({ dist[next],next });
}
}
}
}
int main() {
scanf("%lld %lld %lld", &n, &m, &k);
for (ll i = 1; i <= m; i++) {
scanf("%lld %lld %lld", &a, &b, &c);
v[b].push_back({ a, c });
}
for (ll i = 1; i <= n; i++)
dist[i] = 1e18;
for (ll i = 1; i <= k; i++)
{
ll st;
scanf("%lld", &st);
dist[st] = 0;
pq.push({0,st});
}
dijk();
for (ll i = 1; i <= n; i++)
{
if (Max < dist[i]&&dist[i]!=1e18)
{
Max = dist[i];
Maxi = i;
}
}
printf("%lld\n", Maxi);
printf("%lld\n", Max);
return 0;
}