ACM ICPC World Finals 2016

문제 링크

C. Ceiling Function

$K$개의 노드로 구성된 Binary Search Tree가 $N$개 주어진다. 이 때 서로 다른 모양을 갖는 BST의 개수를 구하는 문제다.

구조체를 써서 BST를 구현하고 두 노드에 대해 각 노드를 루트로한 서브트리가 같은지 비교해주는 재귀 함수를 구현하여 쉽게 해결할 수 있다.

?

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

#include <bits/stdc++.h> using namespace std;   int N, M; int A[21];   struct NODE {     NODE(int val=0): val(val) { left = right = 0; }     int val;     NODE *left, *right; } *root[51];   bool identical(NODE *a, NODE *b) {     if ((bool)a->left != (bool)b->left || (bool)a->right != (bool)b->right) return 0;     bool ret = 1;     if (a->left) ret &= identical(a->left, b->left);     if (a->right) ret &= identical(a->right, b->right);     return ret; }   int main() {     scanf("%d%d", &N, &M);     for (int i=1;i<=N;i++){         for (int j=1;j<=M;j++) scanf("%d", A+j);         root[i] = new NODE(A[1]);         for (int j=2;j<=M;j++){             NODE *now = root[i];             for (;;){                 if (A[j] < now->val){                     if (now->left) now = now->left;                     else{                         now->left = new NODE(A[j]);                         break;                     }                 }else{                     if (now->right) now = now->right;                     else{                         now->right = new NODE(A[j]);                         break;                     }                 }             }         }     }     int ans = 0;     for (int i=1;i<=N;i++){         bool sw = 0;         for (int j=1;j<i;j++) if (identical(root[j], root[i])){ sw = 1; break; }         if (!sw) ans++;     }     printf("%d\n", ans); }

E. Forever Young

수 $Y$를 $b$ 진법으로 나타냈을 때, 0부터 9 사이의 수로 이루어져야하고, 그 수를 10진수처럼 읽었을 때 $L$이상이어야 한다. 이 때 가능한 $b$ 중 최대값을 구하는 문제다.

우선 $b$가 충분히 큰 수인 경우, $b$진법의 자리수가 적을 것이다. 자리수가 5 이하인 경우, $b$진법으로 나타냈을 때 수를 정해놓고 이분탐색을 통해 해당 $b$를 계산하는 방법으로 해결할 수 있다. 만약 $b < 10^{18 / 4} \leq 31,623$으로 충분히 작은 경우에 대해서는 직접 $b$를 정해놓고 확인할 수 있다. $b \geq 10$ 이므로 문자열을 통한 대소비교를 할 필요가 없다.

?

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

#include <bits/stdc++.h> using namespace std;   typedef long long lld;   lld Y, L;   int main() {     scanf("%lld%lld", &Y, &L);     lld ans = 10;     for (int i=0;i<10;i++) for (int j=0;j<10;j++) for (int k=0;k<10;k++) for (int l=0;l<10;l++) for (int o=0;o<10;o++){         lld s = max({i, j, k, l, o})+1, e = Y, b = 0;         while (s <= e){             lld m = (s+e)>>1, v = 0;             if (i && (m > Y/m || m*m > Y/m || m*m*m > Y/m)){ e = m-1; continue; }             if (j && (m > Y/m || m*m > Y/m)){ e = m-1; continue; }             if (k && (m > Y/m)){ e = m-1; continue; }             if (l && (m > Y)){ e = m-1; continue; }             v = m * m * m * m * i + m * m * m * j + m * m * k + m * l + o;             if (v > Y) e = m-1;             else if (v == Y){ b = m; break; }             else s = m+1;         }         lld n  = o + l*10 + k*100 + j*1000 + i*10000;         if (b && L <= n) ans = max(ans, b);     }     for (int i=11;;i++){         if ((lld)i*i*i > Y/i) break;         bool sw = 0; lld n = 0, ten = 1;         for (lld v=Y;v;v/=i){             if (v%i > 9){ sw = 1; break; }             n += v%i * ten; ten *= 10;         }         if (!sw && n >= L) ans = max(ans, (lld)i);     }     printf("%lld\n", ans); }

L. Swap Space

$N$개의 디스크가 있다. 각 디스크에 대해 포맷 전에 포함하는 데이터 용량은 $a$이며, 포맷 후 디스크의 용량은 $b$이다. 각 디스크는 포맷 전에 포함되어있는 데이터를 다른 곳으로 옮겨 백업해야한다. 이 때, 모든 디스크를 포맷하기 위해 마련해야하는 추가 공간의 최소 용량을 구하는 문제다.

디스크를 두 종류를 나눠 생각할 수 있다.

$a \leq b$ 인 경우에 대해 먼저 생각하자. $a$가 작은 순서로 정렬한 뒤에 순서대로 처리한다. 남은 공간이 $a$보다 적으면 추가 공간을 새로 구입하고 아니면 그 공간에 데이터를 백업하고 포맷하는 방식으로 처리한다. 이 때 디스크를 포맷할 때마다 $b - a$ 만큼 총 공간이 증가하므로 최적이다.

이제 $a > b$ 인 경우에 대해 해결하면 된다. 포맷을 다 마친 최종 상태에서 거꾸로 생각해보자. 마지막 포맷을 번복하면 $a - b$ 만큼 총 공간이 증가하는 꼴이 될 것이다. 이 때 추가 공간을 최소로 구입하기 위해서는 $b$가 작은 것을 뒤에 포맷하면 된다. $a \leq b$ 인 경우와 비슷하게 포맷을 $b$의 역순으로 해주면 이 때도 최적이다.

?

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

#include <bits/stdc++.h> using namespace std;   #define MAXN 1000006 typedef long long lld;   int N; struct Z{     int a, b; } A[MAXN];   int main() {     scanf("%d", &N);     for (int i = 1; i <= N; i++) scanf("%d%d", &A[i].a, &A[i].b);     sort(A + 1, A + N + 1, [](const Z &a, const Z &b){         int p = a.a <= a.b ? -1 : 1, q = b.a <= b.b ? -1 : 1;         if (p != q) return p < q;         if (p == -1) return a.a < b.a;         return a.b > b.b;     });     lld ans = 0, free = 0;     for (int i = 1; i <= N; i++){         if (free >= A[i].a) free += -A[i].a + A[i].b;         else{             ans += A[i].a - free;             free = A[i].b;         }     }     printf("%lld\n", ans); }

G. Oil

서로 만나지 않는 수평 선분 $N$개가 있다. 수평이 아닌 직선을 그어 직선이 지나는 수평 선분 길이 합의 최대값을 구하는 문제다.

답이 되는 직선이 있다고 하자. 이 직선이 지나는 선분들이 유지되도록 적절히 좌우로 움직이면 어떤 선분의 끝 점에 걸치도록 할 수 있다. 즉, 답이 되는 직선 중 하나는 어떤 선분의 끝 점을 지난다.

이 특성을 이용해서 선분의 끝 점 중 하나를 정한다. 그리고 이 점을 지나는 직선 중 지나는 수평 선분 길이 합이 최대가 되는 직선을 구한다. 이 때 직선을 180도 돌리는 것 처럼 보이지만, 아래 부분에 해당하는 선분들을 점대칭 시켜서 윗부분으로 옮기면 반직선을 180도 돌리는 것처럼 되어 쉽게 해결할 수 있다. 이 문제는 결국 구간들이 주어지고 지나는 구간 길이 합이 제일 큰 수직선을 구하는 문제와 같게 된다.

?

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

#include <bits/stdc++.h> using namespace std;   #define MAXN 2004 #define pb push_back #define sz(v) ((int)(v).size()) #define all(v) (v).begin(), (v).end() typedef long long lld;   int N; int X1[MAXN], X2[MAXN], Y[MAXN];   struct Z{     int x, y, t; };   int ccw(int ax, int ay, int bx, int by, int cx, int cy) {     lld k = (lld)(bx-ax)*(cy-ay) - (lld)(cx-ax)*(by-ay);     if (k > 0) return 1;     if (k) return -1;     return 0; }   int main() {     scanf("%d", &N);     for (int i=1;i<=N;i++){         scanf("%d%d%d", X1+i, X2+i, Y+i);         if (X1[i] > X2[i]) swap(X1[i], X2[i]);     }     lld ans = 0;     for (int i=1;i<=N;i++) for (int tp=0;tp<2;tp++){         int x = tp ? X2[i] : X1[i];         vector <Z> arr;         for (int j=1;j<=N;j++) if (Y[i] != Y[j]){             if (Y[j] > Y[i]){                 arr.pb({-X1[j]+x, Y[j]-Y[i], X2[j]-X1[j]});                 arr.pb({-X2[j]+x, Y[j]-Y[i], X1[j]-X2[j]});             }else{                 arr.pb({X1[j]-x, Y[i]-Y[j], X1[j]-X2[j]});                 arr.pb({X2[j]-x, Y[i]-Y[j], X2[j]-X1[j]});             }         }         sort(all(arr), [](const Z &a, const Z &b){             int k = ccw(0, 0, a.x, a.y, b.x, b.y);             if (k) return k > 0;             return a.t > b.t;         });         lld sum = X2[i]-X1[i];         ans = max(ans, sum);         for (Z &z: arr){             sum += z.t;             ans = max(ans, sum);         }     }     printf("%lld\n", ans); }

K. String Theory

작은 따옴표(')가 들어있는 문자열 중에 특정 문자열을 k-quotation이라고 정의한다. 문제에서 문자열에서 연속된 작은 따옴표 수들이 수열로 주어질 때, 문자열이 k-quotation인 경우 가장 큰 k를 구하는 문제다.

k-quotation의 특징은 양 옆에 k개의 연속된 작은 따옴표와 그 사이에 (k-1)-quotation이 나열되어 있다는 것이다. 따라서 만약 문자열이 k-quotation이라면 작은 따옴표가 왼쪽에 연속해서 k개, k-1개, ..., 2개, 1개 그리고 오른쪽에 1개, 2개, ..., k-1개, k개 이런식으로 있어야한다. 이제 그 사이 있는 따옴표 배열에 따라 k-quotation인지 아닌지가 결정되는 것으로 생각할 수 있다. 하지만 아주 단순하게 그 사이에 있는 작은 따옴표의 개수가 짝수라면 이 문자열은 k-quotation이다. 왜냐하면 그 사이에 있는 모든 작은 따옴표를 모두 1-quotation으로 봐도 무방하기 때문이다. 만약 그 사이에 있는 작은 따옴표의 개수가 홀수라면 전체 따옴표의 개수가 홀수가 되기 때문에 k-quotation이 될 수 없다.

?

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

#include <bits/stdc++.h> using namespace std;   int N; int A[101]; int main() {     scanf("%d", &N);     int sum = 0;     for (int i=1;i<=N;i++) scanf("%d", A+i), sum += A[i];     if (sum&1){ puts("no quotation"); return 0; }     int ans = sum == 2 ? 1 : 0;     for (int k=2;;k++){         if (sum < k*(k+1)) break;         int t = 1, left = A[1];         bool fail = 0;         for (int i=k;i;i--){             if (!left) left += A[++t];             if (left < i) fail = 1;             left -= i;         }         t = N, left = A[N];         for (int i=k;i;i--){             if (!left) left += A[--t];             if (left < i) fail = 1;             left -= i;         }         if (!fail) ans = k;     }     if (!ans) puts("no quotation");     else printf("%d\n", ans); }

D. Clock Breaking

4개의 숫자를 표시하는 LED 시계가 있다. 어떤 부분은 항상 꺼져있고, 어떤 부분은 항상 켜져있고, 어떤 부분은 잘 동작한다. 어떤 시각부터 연속해서 n분 동안의 상태가 입력으로 주어졌을 때, 시계의 각 LED판의 상황을 구하는 문제다.

가능한 모든 시작시각에 대해 테스트를 해보고 판의 상황을 유추해보면되는 구현 문제다. 각 부분에 대해 상황을 비트로 표현하면 보다 쉽게 해결할 수 있다.

?

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> using namespace std;   #define mp make_pair typedef pair<int, int> pii;   int N; char A[101][8][23];   void print_digit(int x, int d, char board[6][23]) {     vector <pii> pos[10] = {         {{1, 1}, {1, 2}, {2, 0}, {2, 3}, {3, 0}, {3, 3}, {5, 0}, {5, 3}, {6, 0}, {6, 3}, {7, 1}, {7, 2}}, // 0         {{2, 3}, {3, 3}, {5, 3}, {6, 3}}, // 1         {{1, 1}, {1, 2}, {2, 3}, {3, 3}, {4, 1}, {4, 2}, {5, 0}, {6, 0}, {7, 1}, {7, 2}}, // 2         {{1, 1}, {1, 2}, {2, 3}, {3, 3}, {4, 1}, {4, 2}, {5, 3}, {6, 3}, {7, 1}, {7, 2}}, // 3         {{2, 0}, {2, 3}, {3, 0}, {3, 3}, {4, 1}, {4, 2}, {5, 3}, {6, 3}}, // 4         {{1, 1}, {1, 2}, {2, 0}, {3, 0}, {4, 1}, {4, 2}, {5, 3}, {6, 3}, {7, 1}, {7, 2}}, // 5         {{1, 1}, {1, 2}, {2, 0}, {3, 0}, {4, 1}, {4, 2}, {5, 0}, {5, 3}, {6, 0}, {6, 3}, {7, 1}, {7, 2}}, // 6         {{1, 1}, {1, 2}, {2, 3}, {3, 3}, {5, 3}, {6, 3}}, // 7         {{1, 1}, {1, 2}, {2, 0}, {2, 3}, {3, 0}, {3, 3}, {4, 1}, {4, 2}, {5, 0}, {5, 3}, {6, 0}, {6, 3}, {7, 1}, {7, 2}}, // 8         {{1, 1}, {1, 2}, {2, 0}, {2, 3}, {3, 0}, {3, 3}, {4, 1}, {4, 2}, {5, 3}, {6, 3}, {7, 1}, {7, 2}}, // 9     };     for (auto &p: pos[d]) board[p.first][x+p.second] = 'X'; }   void print(int h, int m, char board[8][23]) {     for (int i=1;i<8;i++){         for (int j=1;j<22;j++) board[i][j] = '.';         board[i][22] = 0;     }     if (h/10) print_digit(1, h/10, board);     print_digit(6, h%10, board);     board[3][11] = board[5][11] = 'X';     print_digit(13, m/10, board);     print_digit(18, m%10, board); }   void cmp(char org[8][23], char inp[8][23], char status[8][23]) {     for (int i=1;i<8;i++) for (int j=1;j<22;j++) status[i][j] = 7;     for (int i=1;i<8;i++) for (int j=1;j<22;j++){         int real = org[i][j] == 'X';         int cur = inp[i][j] == 'X';         if (real && cur) status[i][j] &= 3;         if (!real && cur) status[i][j] &= 2;         if (real && !cur) status[i][j] &= 4;         if (!real && !cur) status[i][j] &= 5;     } }   void combine(char to[8][23], char tar[8][23], int type=1) {     for (int i=1;i<8;i++) for (int j=1;j<22;j++){         if (type == 1) to[i][j] &= tar[i][j];         else to[i][j] |= tar[i][j];     } }   bool poss(int h, int m, char status[8][23]) {     for (int i=1;i<8;i++) for (int j=1;j<22;j++) status[i][j] = 7;     for (int i=1;i<=N;i++){         char tmp[8][23], stmp[8][23];         print(h, m, tmp);         cmp(tmp, A[i], stmp);         combine(status, stmp);         m++;         if (m == 60) m = 0, h++;         if (h == 24) h = 0;     }     for (int i=1;i<8;i++) for (int j=1;j<22;j++) if (!status[i][j]) return 0;     return 1; }   int main() {     scanf("%d", &N);     for (int i=1;i<=N;i++){         for (int j=1;j<8;j++) scanf("%s", A[i][j]+1);     }     char status[8][23] = {0, };     for (int i=1;i<8;i++) for (int j=1;j<22;j++) status[i][j] = 0;     bool exists = 0;     for (int h=0;h<24;h++){         for (int m=0;m<60;m++){             char tmp[8][23];             if (poss(h, m, tmp)){                 exists = 1;                 combine(status, tmp, 2);             }         }     }     if (!exists){ puts("impossible"); return 0; }     for (int i=1;i<8;i++) for (int j=1;j<22;j++) if (!status[i][j]){ puts("impossible"); return 0; }     char tmp[8][23];     print(88, 88, tmp);     for (int i=1;i<8;i++){         for (int j=1;j<22;j++){             if (tmp[i][j] == '.') printf(".");             else printf("%c", "-W1?0???"[status[i][j]]);         }         puts("");     } }

A. Balanced Diet

매 순간 다이어트 목적에 맞게 사탕을 먹을 때, 추가로 먹을 수 있는 사탕 개수의 최대값을 구하는 문제다.

무슨 사탕을 먹는 것이 제일 좋을까? 종류에 따라 너무 빨리 먹어서도 안되고 너무 늦게 먹어서도 안된다. 즉, 사탕 종류마다 먹을 수 있는/먹어야되는 순간이 정해지게 된다. 그러면 현재 먹을 수 있는 사탕 종류들이 있다. 현재 먹을 수 있는 사탕 종류들 중에 먹어야되는 순간이 제일 짧은 사탕 종류를 먼저 먹는 것이 항상 좋다. 문제에서 주어진 부등식을 통해 사탕 종류를 먹을 수 있게 되는 순간과 언제까지 먹어야되는지를 계산할 수 있다.

하지만 무한히 많은 사탕을 먹을 수 있는 경우도 존재한다. $f_i$의 분모를 $M$이라고 하자. 추가적으로 $M$개의 사탕을 먹었다면, 그 것과 똑같은 순서로 $M$개의 사탕을 다시 먹어도 다이어트 조건을 만족한다. 그러므로 $M$개 이상의 사탕을 추가적으로 먹을 수 있다면, 무한히 많은 사탕을 먹을 수 있다는 것이다.

?

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

#include <bits/stdc++.h> using namespace std;   #define MAXN 100005 #define mp make_pair typedef long long lld; typedef pair<int, int> pii;   int N, M, K; int A[MAXN], B[MAXN]; int S[MAXN], E[MAXN]; priority_queue <pii> can_eat, not_yet;   void update(int n) {     S[n] = (lld)B[n]*M / A[n];     E[n] = ((lld)(B[n]+1)*M - 1) / A[n]; }   int main() {     scanf("%d%d", &N, &K);     for (int i=1;i<=N;i++) scanf("%d", A+i), M += A[i];     for (int i=1;i<=K;i++){         int t; scanf("%d", &t);         B[t]++;     }     for (int i=1;i<=N;i++){         update(i);         not_yet.push(mp(-S[i], i));     }     for (int i=K;i<K+M;i++){         while (!not_yet.empty() && -not_yet.top().first <= i){             int n = not_yet.top().second; not_yet.pop();             can_eat.push(mp(-E[n], n));         }         if (can_eat.empty() || -can_eat.top().first < i){ printf("%d\n", i-K); return 0; }         int n = can_eat.top().second; can_eat.pop();         B[n]++; update(n);         not_yet.push(mp(-S[n], n));         if (!can_eat.empty() && -can_eat.top().first <= i){ printf("%d\n", i-K); return 0; }     }     puts("forever"); }

B. Branch Assignment

정점이 $N$개고 간선이 $R$개인 방향성 그래프가 주어진다. $1$번 정점부터 $B$번 정점은 특별한 정점이고, 특별한 정점들을 $S$개의 그룹으로 나눠야한다. 그룹마다 비용을 정의할 수 있는데, 그룹의 비용은 그룹에 속해 있는 모든 정점 순서쌍 $(i, j)$들의 비용 합이다. 정점 순서쌍 $(i, j)$의 비용은 $i$번 정점에서 $j$번 정점으로 $B+1$번 정점을 거쳐가는 최단 거리다. $B$개의 특별한 정점을 $S$개의 그룹으로 나누고 그룹 비용의 합을 최소화하는 문제다.

특별한 $i$번 정점이 크기가 $K_i$인 그룹에 속해있다고 하자. $i$번 정점이 전체 비용에 미치는 영향은 $(K_i-1)(\text{dist}(i, B+1) + \text{dist}(B+1, i))$ 만큼인 것을 알 수 있다. 즉, $i$번 정점을 기준으로 볼 때 비용이 그룹의 크기에 영향을 받지 어떤 정점들과 함께 그룹에 있는지는 중요하지 않다는 것이다.

따라서 $S$개 그룹의 크기를 미리 정했다고 했을 때, $V_i = \text{dist}(i, B+1) + \text{dist}(B+1, i)$ 값이 큰 정점이 작은 그룹에 들어가고, $V_i$ 값이 작은 정점이 큰 그룹에 들어가는 것이 최적이다. 즉, $V_i$ 순으로 특별한 정점을 정렬하고 일렬로 나타내었을 때, 같은 그룹에 속한 정점들은 연속되게 그룹을 나눠도 최적해를 구할 수 있다. 이 때 우리는 아래와 같은 DP배열을 정의할 수 있다.

$D[c][i]$ = $V_i$ 값 순으로 정렬해 일렬로 나타날 때, 때 첫 번째 정점부터 $i$번째 정점까지 그룹을 $c$개로 나누었을 때 최소 비용

$D[c][i] = \min_{k<i}(D[c-1][k] + (i-k-1)(V_{k+1}+V_{k+2}+\dots+V_i)$

DP 시간복잡도는 $O(SB^2)$이지만, Divide & Conquer Optimization을 통해 $O(SB \lg B)$로 줄일 수 있다. 이 경우 비용 함수 $C[i][j] = (j-i-1)(V_{i+1}+V_{i+2}+\dots+V_j)$가 사각부등식을 만족하기 때문에 Divide & Conquer Optimization을 이용할 수 있다.

?

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

#include <bits/stdc++.h> using namespace std;   #define MAXN 5003 #define pb push_back typedef pair<int, int> pii; typedef long long lld;   int N, B, K, M; int P[MAXN], Q[MAXN], A[MAXN], V[MAXN]; lld D[MAXN], E[MAXN], S[MAXN]; vector <pii> con[MAXN], rcon[MAXN];   void dijkstra(int st, int dist[], vector<pii> conn[]) {     for (int i=1;i<=N;i++) dist[i] = 1e9;     priority_queue <pii> que;     dist[st] = 0; que.push({0, st});     while (!que.empty()){         int q = que.top().second, d = -que.top().first; que.pop();         if (d != dist[q]) continue;         for (auto &p: conn[q]){             int v = d + p.second, t = p.first;             if (dist[t] > v)                 dist[t] = v, que.push({-v, t});         }     } }   void dfs(int s, int e, int p, int q) {     if (s > e) return;     int m = (s+e)>>1, opt;     D[m] = 1e18;     for (int k=p;k<=q&&k<m;k++){         lld v = E[k] + (lld)(m-k-1)*(S[m]-S[k]);         if (D[m] > v)             D[m] = v, opt = k;     }     dfs(s, m-1, p, opt);     dfs(m+1, e, opt, q); }   int main() {     scanf("%d%d%d%d", &N, &B, &K, &M);     for (int i=1;i<=M;i++){         int a, b, c;         scanf("%d%d%d", &a, &b, &c);         con[a].pb({b, c});         rcon[b].pb({a, c});     }     dijkstra(B+1, P, con);     dijkstra(B+1, Q, rcon);     for (int i=1;i<=B;i++) A[i] = i, V[i] = P[i]+Q[i];     sort(A+1, A+B+1, [](const int &a, const int &b){         return V[a] < V[b];     });     for (int i=1;i<=B;i++) E[i] = 1e18, S[i] = S[i-1] + V[A[i]];     for (int i=1;i<=K;i++){         dfs(i, B, 0, B);         for (int j=0;j<=B;j++) E[j] = D[j];     }     printf("%lld\n", D[B]); }