백준 11817 - Robots and Oil Transportation System (C++)

문제

• 문제 링크

  
   BOJ 11817 - Robots and Oil Transportation System 
  

• 문제 요약

$N$개의 정점으로 이루어진 그래프가 주어진다.
두 로봇이 시작 정점 $s_1, s_2$에서 임의의 단절선이 잇는 서로 다른 두 정점에 도달하려 한다.

어떤 단절선에 대해, 더 나중에 도달한 로봇을 기준으로 시간을 측정한다.
이 시간을 최대한 짧게 하도록 하는 단절선을 선택할 때, 걸리는 최소 시간을 구해보자.


• 제한

TL : $2$ sec, ML : $256$ MB




$2 ≤ N, M ≤ 10^5$

$1 ≤ w_i ≤ 10^3$

주어지는 그래프에 적어도 하나의 단절선이 존재함이 보장된다.

알고리즘 분류

• 그래프 이론 (graphs)
• 단절점과 단절선 (articulation)
• 다익스트라 (dijkstra)

풀이

단절선을 신경쓰기 전에, 항상 최단 거리로 이동해야 최소 시간을 맞출 수 있다.
이는 다익스트라를 이용해 전처리 해둘 수 있다.

두 로봇의 시작정점 $s_1, s_2$부터의 최단 거리 테이블을 모두 채워넣자.

$dist[$$0$$][i]$ : $s_1$에서 $i$에 도달하는 최소 비용.

$dist[$$1$$][i]$ : $s_2$에서 $i$에 도달하는 최소 비용.

이제 문제의 요구사항 그대로, 단절선들을 모두 찾아내보자.

구체적으로 $now$→$nxt$로 향하는 간선이 단절선임을 알 때, 다음의 값을 고려하여 답을 결정할 수 있다.

$s1$의 로봇이 $now$로 간다면, 걸리는 시간 $t_1 =$ $max(dist[0][now], dist[1][nxt])$

$s1$의 로봇이 $nxt$로 간다면, 걸리는 시간 $t_2 =$ $max(dist[0][nxt], dist[1][now])$

존재하는 모든 단절선에 대해 $ans =$ $min(t_1, t_2)$

전체 코드

#include<bits/stdc++.h>
#define N 100001
using namespace std;
 
vector <pair<int, int>> Gr[N];
int in[N], dist[2][N];
int n, m, s1, s2;
 
void Init()
{
    ios_base::sync_with_stdio(0); cin.tie(0);
    memset(dist, 0x3f3f3f3f, sizeof dist);
 
    cin >> n >> m;
    for (int u, v, w; m--;)
    {
        cin >> u >> v >> w;
        Gr[u].emplace_back(v, w);
        Gr[v].emplace_back(u, w);
    }
    cin >> s1 >> s2;
}
void Dijkstra(int u, int s)
{
    priority_queue <pair<int, int>> pq;
    for (pq.push({ dist[u][s] = 0, s }); pq.size();)
    {
        auto [cost, now](pq.top()); pq.pop();
        if (-cost <= dist[u][now])
            for (auto& [nxt, weight] : Gr[now])
            {
                int temp(weight - cost);
                if (temp < dist[u][nxt])
                    pq.push({ -(dist[u][nxt] = temp), nxt });
            }
    }
}
 
int cur, ans(2e9);
int getArtEdge(int now, int prev)
{
    int _min(1e9); in[now] = ++cur;
    for (auto& [nxt, weight] : Gr[now])
        if (nxt ^ prev)
        {
            if (!in[nxt])
            {
                int temp(getArtEdge(nxt, now));
                if (temp > in[now])
                {
                    int t1(max(dist[0][now], dist[1][nxt]));
                    int t2(max(dist[0][nxt], dist[1][now]));
                    ans = min(ans, min(t1, t2));
                }
                _min = min(_min, temp);
            }
            _min = min(_min, in[nxt]);
        }
    return _min;
}
int main()
{
    Init();
    Dijkstra(0, s1);
    Dijkstra(1, s2);
    getArtEdge(1, 1);
    cout << ans;
}

comment

끝