백준15777 Xtreme NP-hard Problem?!

작성일 | In

문제 링크

  • http://icpc.me/15777

시간복잡도

  • $O(N+M)$

풀이

$N < K$이거나 $M < K$이면 간선 $K$개로 이루어진 경로가 존재하지 않습니다. 그러므로 문제에 있는 조건 $\min(N, M, K) \leq X$는 $K \leq X$라고 생각할 수 있습니다.
$K$가 1, 2, 3, 4, 5일 때의 풀이를 각각 알아봅시다.

K = 1

1과 N을 연결하는 간선이 있는지 확인하고, 있으면 그 간선의 가중치를 출력하면 됩니다.

K = 2

경로를 1 - X - N 꼴로 표현할 수 있습니다.
1과 N에서 동시에 갈 수 있는 정점을 모두 구한 뒤, dst(1, X) + dst(X, N)의 최솟값을 출력하면 됩니다.

K = 3

경로를 1 - X - Y - N 꼴로 표현할 수 있습니다.

A[x] = 1과 x를 연결하는 간선의 가중치, B[y] = y와 N을 연결하는 간선의 가중치로 정의합시다. 이때 간선이 존재하지 않는다면 무한대로 설정하면 됩니다.
모든 간선 (x, y)를 보면서, A[x] + dst(x, y) + B[y]의 최솟값을 구하면 됩니다.

K = 4

경로를 1 - X - Y - Z - N 꼴로 표현할 수 있습니다.

1 초과 N 미만인 모든 정점 Y를 보면서, Y와 연결된 두 정점 X, Z(X ≠ Z)에 대해 A[X] + dst(X, Y) + dst(Y, Z) + B[Z]의 최솟값을 구하면 됩니다.
X, Y, Z가 모두 서로 달라야 하기 때문에, (A[X] + dst(X, Y)) 중 가장 작은 2개, (dst(Y, Z) + B[Z]) 중 가장 작은 2개를 구해서 X, Y, Z가 모두 다른 경우 최솟값을 갱신해주면 됩니다.

K = 5

경로를 1 - W - X - Y - Z - N 꼴로 표현할 수 있습니다.

A’[X] = 1 - W - X 꼴의 경로 중 가중치 최솟값, B’[Y] = Y - Z - N 꼴의 경로 중 가중치 최솟값으로 정의합시다.
모든 간선 (X, Y)를 보면서, A’[X] + dst(X, Y) + B’[Y]의 최솟값을 구하면 됩니다.

W, X, Y, Z가 모두 서로 달라야 하기 때문에, A’와 B’ 각각 가장 작은 3개를 저장하면 답을 구할 수 있습니다.

전체 코드

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
#include <bits/stdc++.h>
#define x first
#define y second
#define all(v) v.begin(), v.end()
#define compress(v) sort(all(v)), v.erase(unique(all(v)), v.end())
using namespace std;

typedef long long ll;
typedef pair<ll, ll> p;
const ll inf = 0x3f3f3f3f3f3f3f3f;

int n, m, k;
vector<p> g[1010101];
ll a[1010101], b[1010101];

inline void print(ll x){ cout << (x < inf ? x : -1); }

void solve_1(){
    ll mn = inf;
    for(auto i : g[1]) if(i.x == n) mn = min(mn, i.y);
    print(mn);
}

void solve_2(){
    ll mn = inf;
    for(auto i : g[1]) a[i.x] = min(a[i.x], i.y);
    for(auto i : g[n]) b[i.x] = min(b[i.x], i.y);
    for(int i=2; i<n; i++) mn = min(mn, a[i] + b[i]);
    print(mn);
}

void solve_3(){
    ll mn = inf;
    for(auto i : g[1]) a[i.x] = min(a[i.x], i.y);
    for(auto i : g[n]) b[i.x] = min(b[i.x], i.y);
    for(int i=2; i<n; i++) if(a[i] < inf) {
        for(auto j : g[i]) if(j.x != 1 && j.x != n && b[j.x] < inf) {
            mn = min(mn, a[i] + j.y + b[j.x]);
        }
    }
    print(mn);
}

void solve_4(){
    ll mn = inf;
    for(auto i : g[1]) a[i.x] = min(a[i.x], i.y);
    for(auto i : g[n]) b[i.x] = min(b[i.x], i.y);

    vector<p> u, v; u.reserve(3); v.reserve(3);
    for(int i=2; i<n; i++){
        u.clear(); v.clear();
        for(auto j : g[i]) if(j.x != 1 && j.x != n) {
            if(a[j.x] < inf) u.emplace_back(a[j.x] + j.y, j.x);
            if(b[j.x] < inf) v.emplace_back(b[j.x] + j.y, j.x);
            if(u.size() == 3) sort(all(u)), u.pop_back();
            if(v.size() == 3) sort(all(v)), v.pop_back();
        }
        for(int j=0; j<2; j++) for(int k=0; k<2; k++) {
            if(j < u.size() && k < v.size() && u[j].y != v[k].y) {
                mn = min(mn, u[j].x + v[j].x);
            }
        }
    }
    print(mn);
}

vector<p> u[1010101], v[1010101];
void solve_5(){
    ll mn = inf;
    for(auto i : g[1]) a[i.x] = min(a[i.x], i.y);
    for(auto i : g[n]) b[i.x] = min(b[i.x], i.y);
    for(int i=2; i<n; i++) u[i].reserve(4), v[i].reserve(4);
    for(int i=2; i<n; i++){
        for(auto j : g[i]) if(j.x != 1 && j.x != n) {
            if(a[j.x] < inf) u[i].emplace_back(a[j.x] + j.y, j.x);
            if(b[j.x] < inf) v[i].emplace_back(b[j.x] + j.y, j.x);
            if(u[i].size() == 4) sort(all(u[i])), u[i].pop_back();
            if(v[i].size() == 4) sort(all(v[i])), v[i].pop_back();
        }
    }
    for(int i=2; i<n; i++) for(auto j : g[i]) if(j.x != 1 && j.x != n) {
        for(int k=0; k<3; k++) for(int s=0; s<3; s++){
            if(k >= u[i].size() || s >= v[j.x].size()) continue;
            if(u[i][k].y == j.x || v[j.x][s].y == i ||  u[i][k].y == v[j.x][s].y) continue;
            mn = min(mn, u[i][k].x + j.y + v[j.x][s].x);
        }
    }
    print(mn);
}

int main(){
    ios_base::sync_with_stdio(false); cin.tie(nullptr);
    cin >> n >> m >> k;
    if(n < k || m < k){ cout << -1; return 0; }
    for(int i=0; i<m; i++){
        int s, e, x; cin >> s >> e >> x;
        g[s].emplace_back(e, x);
        g[e].emplace_back(s, x);
    }
    memset(a, 0x3f, sizeof a); memset(b, 0x3f, sizeof b);
    if(k == 1) solve_1();
    if(k == 2) solve_2();
    if(k == 3) solve_3();
    if(k == 4) solve_4();
    if(k == 5) solve_5();
}