1
bool check(int x) {
2
    // 判断 x 是否满足条件
3
}
4

5
void solve() {
6
    // 确定上下界
7
    int l = 1, r = 1e18, ans = -1;
8
    while (l <= r) {
9
        int mid = (l + r) / 2;
10
        if (check(mid)) {
11
            ans = mid;
12
            r = mid - 1; // 如果满足条件，尝试更小的情况
13
        } else {
14
            l = mid + 1; // 否则尝试更大的情况
15
        }
16
    }
17
}

1
// 一维前缀和
2
sum[i] = sum[i - 1] + arr[i];
3
// [l, r]
4
int ans = sum[r] - sum[l - 1];

1
// 二维前缀和
2
sum[i][j] = sum[i - 1][j] + sum[i][j - 1] - sum[i - 1][j - 1] + arr[i][j];
3
// (x1, y1) -> (x2, y2)
4
int ans = sum[x2][y2] - sum[x2][y1 - 1] - sum[x1 - 1][y2] + sum[x1 - 1][y1 - 1];

1
// 一维差分
2
diff[i] = arr[i] - arr[i - 1];
3
// [l, r] + x
4
diff[l] += x;
5
diff[r + 1] -= x;
6
// 前缀和还原
7
diff[i] += diff[i - 1];

1
// 二维差分
2
diff[i][j] = arr[i][j] - arr[i - 1][j] - arr[i][j - 1] + arr[i - 1][j - 1];
3
// (x1, y1) -> (x2, y2) + x
4
diff[x1][y1] += x;
5
diff[x1][y2 + 1] -= x;
6
diff[x2 + 1][y1] -= x;
7
diff[x2 + 1][y2 + 1] += x;
8
// 前缀和还原
9
diff[i][j] += diff[i - 1][j] + diff[i][j - 1] - diff[i - 1][j - 1];

1
bool is_prime(int n) {
2
  if (n < 2) return 0;
3
  for (int i = 2; i <= n / i; i++) {
4
    if (n % i == 0) return false;
5
  }
6
  return true;
7
}

1
void divide(int N)
2
{
3
  int n = N;
4
  for (int i = 2; i <= N / i; i++) {
5
    if (n % i == 0) {
6
      int sum = 0;
7
      while (n % i == 0) {
8
        n /= i;
9
        sum++;
10
      }
11
      cout << i << " " << sum << endl;
12
    }
13
  }
14
  if (n > 1) cout << n << " " << 1 << endl;
15
}

1
const int N = 1000010;
2
int primes[N], cnt;
3
bool vis[N];
4

5
void get_primes(int n) {
6
  for (int i = 2; i <= n; i++) {
7
    if (vis[i]) continue;
8
    // 记录素数
9
    primes[cnt++] = i;
10
    // 筛选倍数
11
    for (int j = i + i; j <= n; j += i) {
12
      vis[j] = true;
13
    }
14
  }
15
}

1
const int N = 1000010;
2
int primes[N], cnt;
3
bool vis[N];
4

5
void get_primes(int n) {
6
  for (int i = 2; i <= n; i++) {
7
    if (!vis[i]) primes[cnt++] = i;
8
    // 在 i 确定的时候可以选取哪几个素数
9
    for (int j = 0; primes[j] * i <= n; j++) {
10
            // 合数 = 最小质因子 * 另一个数
11
      vis[primes[j] * i] = true;
12
            // 如果 primes[j] 是 i 的最小质因子，跳出
13
      if (i % primes[j] == 0) break;
14
     }
15
  }
16
}

1
vector<int> get_divisors(int n)
2
{
3
  vector<int> ans;
4
  for (int i = 1; i <= n / i; i++) {
5
    if (n % i == 0) {
6
      ans.push_back(i);
7
      if (i != n / i) ans.push_back(n / i);
8
    }
9
  }
10
  sort(ans.begin(), ans.end());
11
  return ans;
12
}

1
const int N = 5555;
2
int p[N];
3
int find(int x) {
4
    if (p[x] != x) p[x] = find(p[x]);
5
    return p[x];
6
}
7

8
struct Data{
9
    int u, v, w;
10
};
11
int n, m;
12
bool cmp(Data x, Data y) {
13
    return x.w < y.w;
14
}
15

16
void solve() {
17
    cin >> n >> m;
18
    vector<Data> arr(m);
19
    for (int i = 1; i <= n; i++) p[i] = i;
20
    for (int i = 0; i < m; i++) {
21
        int u, v, w; cin >> u >> v >> w;
22
        arr[i] = {u, v, w};
23
    }
24
    sort(arr.begin(), arr.end(), cmp);
25
    int cnt = 0;
26
    int sum = 0;
27
    // 如果连通，那么至少要 n - 1 条边
28
    for (int i = 0; i < m; i++) {
29
        int u = arr[i].u, v = arr[i].v, w = arr[i].w;
30
        if (find(u) != find(v)) {
31
            p[find(u)] = find(v);
32
            sum += w;
33
            cnt++;
34
        }
35
    }
36
    if (cnt >= n - 1) {
37
        cout << sum << endl;
38
    } else {
39
        cout << "orz" << endl;
40
    }
41
}

1
void solve() {
2
    int n, m; cin >> n >> m;
3
    vector<vector<int>> g(n + 1);
4
    // 入度
5
    vector<int> indeg(n + 1);
6
    for (int i = 0; i < m; i++) {
7
        int u, v; cin >> u >> v;
8
        g[u].push_back(v);
9
        indeg[v]++;
10
    }
11
    queue<int> q;
12
    vector<int> ans;
13
    for (int i = 1; i <= n; i++) {
14
        if (indeg[i] == 0) {
15
            q.push(i);
16
            ans.push_back(i);
17
        }
18
    }
19
    while (!q.empty()) {
20
        int u = q.front(); q.pop();
21
        for (auto v : g[u]) {
22
            indeg[v]--;
23
            if (indeg[v] == 0) {
24
                q.push(v);
25
                ans.push_back(v);
26
            }
27
        }
28
    }
29
    if (ans.size() == n) {
30
        for (int i = 0; i < n; i++) cout << ans[i] << " "; cout << endl;
31
    } else cout << -1 << endl;
32
}

1
#include <bits/stdc++.h>
2
using namespace std;
3
#define int long long
4

5
// N: 最大点的数量
6
// M: 最大边的数量
7
// 无向图的时候记得开 2 倍 M 的空间
8
const int N = 1e5, M = 1e5;
9
int n, m;
10
// h[i]: 存 i 节点的头边号
11
// next[i]: 存 i 边的下个一个边的边号
12
// to[i]: 存 i 边指向的点的编号
13
// w[i]: 存 i 边指向的边的权值
14
int h[N + 1];
15
struct Edge{
16
    int to, w, next;
17
} e[M + 1];
18

19
int cnt = 1;
20

21
// u -> v 权值为 w
22
void add(int u, int v, int w) {
23
    e[cnt].next = h[u];
24
    e[cnt].to = v;
25
    e[cnt].w = w;
26
    h[u] = cnt++;
27
}
28

29
void clear() {
30
    for (int i = 1; i <= n; i++) h[i] = 0;
31
    cnt = 1;
32
}
33

34
void solve() {
35
    cin >> n >> m;
36
    for (int i = 0; i < m; i++) {
37
        int u, v, w; cin >> u >> v >> w;
38
        add(u, v, w);
39
    }
40
    for (int u = 1; u <= n; u++) {
41
        for (int i = h[u]; i; i = e[i].next) {
42
            int v = e[i].to, w = e[i].w;
43
            printf("%d -> %d, w = %d\n", u, v, w);
44
        }
45
    }
46
    clear();
47
}
48

49
signed main() {
50
    ios::sync_with_stdio(0); cin.tie(0);
51
    int T = 1;
52
    // cin >> T;
53
    while (T--) solve();
54
    return 0;
55
}

1
#include <bits/stdc++.h>
2
using namespace std;
3
#define int long long
4
#define PII pair<int, int>
5

6
const int N = 1e5 + 1;
7
vector<PII> g[N];
8
bool vis[N];
9
int d[N];
10
int n, m, s;
11

12
void clear() {
13
    for (int i = 0; i < N; i++) g[i].clear();
14
    fill(d, d + N, LLONG_MAX);
15
    fill(vis, vis + N, false);
16
}
17

18
// vis标记过后的点，最短路已经确定了
19
// 所有的点与源点相连的最短路径，构成了一棵树
20

21
void dijkstra() {
22
    priority_queue<PII, vector<PII>, greater<PII>> heap;
23
    d[s] = 0; heap.push({0, s});
24
    while (!heap.empty()) {
25
        int u = heap.top().second; heap.pop();
26
        if (vis[u]) continue;
27
        vis[u] = true;
28
        for (auto [v, w] : g[u]) {
29
            if (!vis[v] && d[u] + w < d[v]) {
30
                d[v] = d[u] + w;
31
                heap.push({d[v], v});
32
            }
33
        }
34
    }
35
}
36

37
void solve() {
38
    clear();
39
    cin >> n >> m >> s;
40
    for (int i = 0; i < m; i++) {
41
        int u, v, w; cin >> u >> v >> w;
42
        g[u].push_back({v, w});
43
    }
44
    dijkstra();
45
    for (int i = 1; i <= n; i++) cout << d[i] << " "; cout << '\n';
46
}
47

48
signed main() {
49
    ios::sync_with_stdio(0); cin.tie(0);
50
    int T = 1;
51
    // cin >> T;
52
    while (T--) solve();
53
    return 0;
54
}