[HackerRank w7] Savita And Friends

문제: HackerRank or hongjun7's blog

이 문제는 $N$개의 정점과 그들 사이를 잇는 $M$개의 간선이 있는 무방향성 그래프에서 $K$번째 간선 상에 임의의 점 $P$를 잡아 $P$에서 각 정점으로 가는 최단 거리들 중 최대를 최소화 시키는 문제다.

우선 직관적으로 답의 소수점은 x.0 혹은 x.5 꼴임을 알 수 있다. 실수 연산을 피하기 위해 각 간선의 길이에 2를 곱해서 처리한다.

답(최단 거리들 중 최대 값)을 정하여, 가능한지 불가능한지 결정 문제로 바꾸어 이분 검색(혹은 Parametric search)를 통해 해결한다.

답을 $d$라 정했다고 가정하고, 각 지점으로 가는 최단 거리가 $d$ 이하가 될 수 있도록 점 $P$를 잡을 수 있는지 결정하는 방법을 설명하겠다.

문제에서 설명한데로 $K$번째 간선은 $A$와 $B$를 잇는 간선이며, 길이가 $C$라고 하자.

$D_i$를 $A$에서 점 $i$로 가는 최단 거리라고 정의하고,

$E_i$를 $B$에서 점 $i$로 가는 최단 거리라고 정의하자.

이들은 다익스트라 알고리즘(Dijkstra Algorithm)을 통해 $O(N \log_2 N)$ 혹은 $O(N \log_2 M)$ 만에 구할 수 있다.

점 $P$에서 정점 $i$까지 이동 거리 $d$안에 도착 가능한 $P$의 위치들은 최대 2개의 구간으로 표현 가능하다.

정점 $A$에서 점 $P$ 까지의 거리를 $x$라 하자.

1) 점 $P$에서 정점 $A$를 통해 정점 $i$로 가는 경우

만약, $D_i + x > d$ 인 경우 불가능하다.

그렇지 않다면, $0 \leq x \leq d - D_i$를 만족하는 $x$에 대응하는 $P$의 위치가 가능하다.

2) 점 $P$에서 정점 $B$를 통해 정점 $i$로 가는 경우

만약, $E_i + C - x > d$ 인 경우 불가능하다.

그렇지 않다면, $E_i + C - d \leq x \leq C$를 만족하는 $x$에 대응하는 $P$의 위치가 가능하다.

정점 $i$에 대해 이동 거리가 $d$ 이하가 가능한 $P$의 위치들을 구했으므로, $N$개의 정점에 대해 모두 가능한 $P$의 위치가 있는지 확인하여주면된다.

이를 좀 더 간단히 구하기 위해, 반대로 불가능한 $P$의 위치들을 구한다.

이는 정점 $i$에 대해 $\max(d - D_i + 1, 0) \leq x \leq \min(E_i + C - d - 1, C)$를 만족하는 $x$에 대응하는 $P$의 위치들이다. 이제 최대 $N$개의 구간들 중에서 모든 구간에 속하지 않은 $x$ 값을 구하면 된다. 이는 매우 잘 알려진 문제이며, $O(N \log_2 N)$ 만에 해결할 수 있다.

#include <stdio.h> #include <queue> #include <vector> #include <algorithm> using namespace std; #define MAXN 100005 #define mp make_pair #define pb push_back #define sz(v) ((int)(v).size()) #define all(v) (v).begin(),(v).end() typedef long long lld; typedef pair<lld,int> pli; typedef pair<lld,lld> pll; int T,N,M,K,A,B,C; lld D[MAXN],E[MAXN],ans; vector <int> con[MAXN],conv[MAXN]; void dijkstra(int n,lld dist[]) { int i; priority_queue <pli> que; for (i=1;i<=N;i++) dist[i] = 1e17; dist[n] = 0; que.push(mp(0,n)); while (!que.empty()){ int q = que.top().second; lld d = -que.top().first; que.pop(); if (dist[q] != d) continue; for (i=sz(con[q]);i--;){ int k = con[q][i], v = conv[q][i]; if (dist[k] > dist[q]+v) dist[k] = dist[q]+v, que.push(mp(-dist[k],k)); } } } bool proc(lld d,lld &r) { int i; vector <pll> arr; for (i=1;i<=N;i++){ lld p = max(d-D[i]+1,0LL), q = min(E[i]+C-d-1,(lld)C); if (p > q) continue; arr.pb(mp(p,q)); } sort(all(arr)); lld e = -1; for (i=0;i<sz(arr);i++){ if (e+1 < arr[i].first){ r = e+1; return 1; } if (e < arr[i].second) e = arr[i].second; } if (e < C){ r = e+1; return 1; } return 0; } int main() { int i,j,k; for (scanf("%d",&T);T--;){ scanf("%d%d%d",&N,&M,&K); for (i=1;i<=N;i++) con[i].clear(), conv[i].clear(); for (i=1;i<=M;i++){ int a,b,c; scanf("%d%d%d",&a,&b,&c); c <<= 1; con[a].pb(b); conv[a].pb(c); con[b].pb(a); conv[b].pb(c); if (i == K) A = a, B = b, C = c; } dijkstra(A,D); dijkstra(B,E); lld s = 0, e = 1e15, m, d; while (s <= e){ m = (s+e)>>1; if (proc(m,d)) e = m-1, ans = m; else s = m+1; } proc(ans,d); printf("%lld.%d0000 %lld.%d0000\n",d>>1,d&1?5:0,ans>>1,ans&1?5:0); } }