백준[2836] 수상 택시

문제 설명

문제 링크

http://icpc.me/2836

2836번: 수상 택시

풀이

스위핑을 이용하여 풀이할 수 있다.

a에서 태워 b에서 내려준다고 할 때, 상근이가 무조건 M에 도달해야 하기 때문에 a < b인 상황은 자연스럽게 해결이 된다.

하지만 a > b인 상황에서 언제 되돌아가서 내려줄건지 고려를 잘해야 한다.

최단 경로로 가기 위해서는 같은 경로를 여러 번 돌아가면 안 된다. 그렇기 때문에 a -> b와 c -> d로 가는 두 경로가 만약 겹친다면 한 번에 움직여야 한다. 

코드

#include <cstdio>
#include <algorithm>
#include <vector>

using namespace std;
using ll = long long;
using pll = pair<ll, ll>;

vector<pll> v;

int main() {
    ll n, m; scanf("%lld %lld", &n, &m);
    for (ll i = 0; i < n; i++) {
        ll a, b; scanf("%lld %lld", &a, &b);
        if (a > b) v.push_back({b, a});
    }

    sort(v.begin(), v.end());
    ll s = 0, e = 0, res = m;
    for (ll i = 0; i < v.size(); i++) {
        auto [x, y] = v[i];
        if (e < x) {
            res += 2 * (e - s);
            s = x;
            e = y;
        } else {
            e = max(e, y);
        }
    }
    res += 2 * (e - s);
    printf("%lld", res);
}