[BOJ 5551] 쇼핑몰

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

5551번: 쇼핑몰

Tag : dijkstra

 

문제 요약

정점마다 가장 가까운 쇼핑몰과의 거리를 \(A_i\)라 정의할 때 이 \(A_i\)의 최대를 구하는 문제다.

 

풀이

최단경로...->최소.....최대........ 파라메트릭?하면서 뇌절할뻔했다.

가장 멀리 있는 집은 어떠한 간선의 양 끝 또는 간선 위에 존재한다.

그래서 모든 간선을 확인하면서 \(\lceil (dist[s]+dist[e])/2 \rceil\)를 확인하면 된다.

왜 그럴까?

 

파란 정점이 쇼핑몰, 빨간 정점이 간선 양끝의 도시일 때 쇼핑몰을 잡고 쭉 펴면

아래와 같은 형태가 되고 그 길이는 \(\lceil (dist[s]+dist[e])/2 \rceil\)가 된다.

 

이제 열심히 코드짜면 된다.

 

시간복잡도 : \(O(ElogV)\)

 

전체 코드

#include "bits/stdc++.h"
#define pb push_back
#define fi first
#define se second
#define all(x) ((x).begin()), ((x).end())
#define compress(x) sort(all(x)), (x).erase(unique(all(x)),(x).end())
#define siz(x) ((int)((x).size()))
#define endl '\n'
using namespace std;
using ll = long long;
using pi = pair<int,int>;
using pl = pair<ll,ll>;
template<typename T>T rmin(T &a,T b){return a=min<T>(a,b);}
template<typename T>T rmax(T &a,T b){return a=max<T>(a,b);}



int main(){
    ios::sync_with_stdio(0);cin.tie(0);
    
    int N,M,K;cin>>N>>M>>K;
    vector<vector<pair<int,ll>>>v(N+1);
    vector<tuple<int,int,ll>>edge(M);
    for(int i=0;i<M;i++){
        ll x,y,z;cin>>x>>y>>z;
        edge[i]={x,y,z};
        v[x].pb({y,z});v[y].pb({x,z});
    }
    vector<ll>dist(N+1,1e18);
    priority_queue<pair<ll,int>>pq;
    vector<int>chk(N+1);
    for(int i=0;i<K;i++){
        int x;cin>>x;
        dist[x]=0;chk[x]=1;
        pq.push({~0ll,x});
    }
    while(siz(pq)){
        auto [w,cur]=pq.top();pq.pop();
        w=~w;
//        cout<<cur<<' '<<dist[cur]<<' '<<w<<endl;
        if(dist[cur]<w)continue;
        for(auto&[i,j]:v[cur]){
            if(dist[i]>w+j){
                dist[i]=w+j;
                pq.push({~dist[i],i});
            }
        }
    }
//    for(int i=1;i<=N;i++)cout<<i<<' '<<dist[i]<<endl;
    ll ans=0;
    for(auto&[i,j,k]:edge){
//        if(chk[i] or chk[j])continue;
//        cout<<i<<' '<<j<<' '<<(dist[i]+dist[j]+k+1)/2<<endl;
//        cout<<i<<' '<<j<<' '<<dist[i]<<' '<<dist[j]<<endl;
        rmax(ans,(dist[i]+dist[j]+k+1)/2);
    }
    cout<<ans<<endl;
}