백준온라인 17835 [면접보는 승범이네][C++]

 

www.acmicpc.net/problem/17835

17835번: 면접보는 승범이네

---

나의 풀이

사실 이문제는 이문제의 제작자인 데구리형님 에게 약간의 힌트를 예전에 들은적이 있어 그 기억을 더듬어보며 바로 문제를 풀수 있었다.

 

이 문제는 단방향인게 골때리는 점이다.

 

이 문제가 양방향이 였다면 면접장을 기준으로 다익스트라를 돌려보면 모든 마을의 최단거리를 저장하고 모든 마을의 최단거리중 가장 큰 값을 정답의 후보로 올려주면 되는문제였을것이다

 

사실 단방향이여도 다익스트라를 돌릴수 있긴한데 그러면 N이 너무 크기 떄문에 시간초과가 난다.

 

이 문제의 핵심적인 발상은

면접자가 (단방향 간선 집합) A 를 거쳐 면접장소까지가는 최단거리를 계산하는것은

면접장소(가 ?)  (단방향을 뒤집은 간선들의 집합) A' 를 거쳐 면접자에게 가는 것과 같은 경로가 될것이라는 것이다.

 

면접장소가 주체가 될수 있다면 다익스트라 한번이면 풀수 있는 문제로 변할것이다.

 

정리하자면 풀이순서는

1.간선을 모두 뒤집으면서 저장한다

2.면접장소를 기준으로 거리를 0 으로 세팅하고 큐를 이용해 다익스트라를 돌려준다

3.후보를 찾는다 (다익스트라를 돌려주고 나면 dist[i] 는 i면접자가 가능한 가장 가까운 면접장까지의 최단거리가 저장이 될것이다)

 

이렇게 보면 쉬운거같은데 발상자체가 너무 쫌 어려운건아닌거같은데 하....아무튼 생각못하면 풀기 힘들다

체감상 www.acmicpc.net/problem/2887 이문제랑 비슷했다 풀어본적이 없으면 나의 능지로는 생각하기 힘들었다....

---

소스

#include <bits/stdc++.h>
#define INF 0x3f3f3f3f3f3f3f
using namespace std;
using ll = long long;
using pii = pair<int, int>;
using vpii = vector<pii>;

vpii edge[100001];
ll d[100001];
int main(){
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    int n,m,k;
    cin>>n>>m>>k;
    int a,b,c;
    for(int i=0;i<m;i++){
        cin>>b>>a>>c;
        edge[a].push_back({b,c});
    }

    for(int i=1;i<=n;i++){
        d[i]=INF;
    }

    queue<int> q;
    for(int i=0;i<k;i++){
        cin>>a;
        q.push(a);
        d[a]=0;
    }
    
    while(!q.empty()){
        int cur = q.front();
        q.pop();
        for(auto x : edge[cur]){
            int next = x.first;
            int cost = x.second;
            ll minCost = cost+d[cur];
            if(minCost<d[next]){
                d[next]=minCost;
                q.push(next);
            }
        }
    }

    int idx;
    ll maxVal=-1;
    for(int i=1;i<=n;i++){
        if(maxVal<d[i]){
            maxVal=d[i];
            idx=i;
        }
    }
    cout<<idx<<"\n"<<maxVal;
    
    
}