并查集、最短路

// Problem: ${json.name}
// Contest: ${json.group}
// URL: ${json.url}
// Memory Limit: ${json.memoryLimit} MB
// Time Limit: ${json.timeLimit} ms
// More thought is needed

#include <bits/stdc++.h>
#define endl '\n'
#define int long long
using namespace std;
const int N = 2e5 + 9;
int pre[N];  //用来说明下一个节点指向
int Hash[N];
int root(int i) {
  return pre[i] = (pre[i] == i ? i : root(pre[i]));
}  // root数组用来找到输入节点的root节点
void merge(int u, int v) { pre[root(u)] = root(v); }  //用于将u节点连接到v节点上
void solve() {
  int n, m;
  cin >> n >> m;
  for (int i = 1; i <= n; i++) pre[i] = i;  //将每个节点初始化为pre指向自己
  for (int i = 1; i <= m; i++) {
    int u, v;
    cin >> u >> v;
    merge(u, v);
  }
  for (int i = 1; i <= n; i++) {
    Hash[root(i)]++;  //桶存储
  }
  vector<int> vec;
  for (int i = 1; i <= n; i++) {
    if (Hash[i]) vec.push_back(Hash[i]);  //存到vec中
  }
  sort(vec.begin(), vec.end());
  for (auto& i : vec) {
    cout << i << " ";
  }
}

signed main() {
  ios::sync_with_stdio(false), cin.tie(nullptr), cout.tie(nullptr);
  solve();
  return 0;
}

// Problem: ${json.name}
// Contest: ${json.group}
// URL: ${json.url}
// Memory Limit: ${json.memoryLimit} MB
// Time Limit: ${json.timeLimit} ms
// More thought is needed

#include <bits/stdc++.h>
#define endl '\n'
#define int long long
using namespace std;

const int N = 1e3 + 9;
int n, m;
struct Edge {  //自定义类型edge用于存储节点的指向节点和路径价值
  int out, value;
};
bitset<N> vis;  // vis做标记
int d[N];       // d数组存储最短路径
vector<Edge> node[N];  //生成edge类型数组,用于存储节点的入,出,价值,有点像桶
void dijkstra(int x) {
  memset(d, 0x3f,
         sizeof(int) * (n + 1));  //设d数组初值为0x3f,使其在下文的比较中覆盖
  d[x] = 0;                       //最初节点的价值为0
  for (int i = 1; i <= n; i++) {  //对所有节点遍历
    int u = 1;
    for (int j = 1; j <= n; j++) {  //寻找最小点
      if (vis[u] || (!vis[j] && d[j] < d[u])) u = j;
    }
    vis[u] = true;                  //标记为true
    for (auto& [v, w] : node[u]) {  //在最小点中找各路径,并计算各路径的价值
      if (!vis[v] && d[v] > d[u] + w) d[v] = d[u] + w;
    }
  }
}

void solve() {
  cin >> n >> m;
  for (int i = 1; i <= m; i++) {
    int u, v, w;
    cin >> u >> v >> w;
    node[u].push_back({v, w});
  }
  dijkstra(1);
  if (d[n] >= 0x3f3f3f3f3f3f) {
    cout << "-1";
  } else
    cout << d[n];
}

signed main() {
  ios::sync_with_stdio(false), cin.tie(nullptr), cout.tie(nullptr);
  solve();
  return 0;
}

// Problem: ${json.name}
// Contest: ${json.group}
// URL: ${json.url}
// Memory Limit: ${json.memoryLimit} MB
// Time Limit: ${json.timeLimit} ms
// More thought is needed

#include <bits/stdc++.h>
#define endl '\n'
#define int long long
using namespace std;

const int N = 2e5 + 9;
int n, m;
struct Edge {  //自定义类型edge用于存储节点的指向节点和路径价值
  int out, value;
  bool operator<(const Edge& v) const {  //自定义运算符
    return value == v.value ? out < v.out : value > v.value;
  }
};
bitset<N> vis;  // vis做标记
int d[N];       // d数组存储最短路径
vector<Edge> node[N];  //生成edge类型数组,用于存储节点的入,出,价值,有点像桶
void dijkstra(int x) {
  memset(d, 0x3f,
         sizeof(int) * (n + 1));  //设d数组初值为0x3f,使其在下文的比较中覆盖
  d[x] = 0;                       //最初节点的价值为0
  priority_queue<Edge> pq;  //用快速队列(堆)来存储,自带维护,小顶堆
  pq.push({x, d[x]});       //先把x存入
  while (
      pq.size()) {  //其实都是一个东西,只是因为小顶堆自带维护功能,代替其挨个找最小
    int a = pq.top().out;
    pq.pop();
    if (vis[a]) continue;
    vis[a] = true;
    for (auto& [y, w] : node[a]) {
      if (!vis[y] && d[y] > d[a] + w) {  //判断
        d[y] = d[a] + w;
        pq.push({y, d[y]});  //压入
      }
    }
  }
}

void solve() {
  cin >> n >> m;
  for (int i = 1; i <= m; i++) {
    int u, v, w;
    cin >> u >> v >> w;
    node[u].push_back({v, w});
  }
  dijkstra(1);
  if (d[n] >= 0x3f3f3f3f3f3f) {
    cout << "-1";
  } else
    cout << d[n];
}

signed main() {
  ios::sync_with_stdio(false), cin.tie(nullptr), cout.tie(nullptr);
  solve();
  return 0;
}

  // Problem: ${json.name}
// Contest: ${json.group}
// URL: ${json.url}
// Memory Limit: ${json.memoryLimit} MB
// Time Limit: ${json.timeLimit} ms
// More thought is needed

#include <bits/stdc++.h>
#define endl '\n'
#define int long long
using namespace std;
const int N = 3e2 + 9;
int node[N][N];  //因为是单向节点,用于存储一个节点到另一个节点的价值
void solve() {
  int n, m, q;
  cin >> n >> m >> q;
  memset(node, 0x3f, sizeof node);
  for (int i = 1; i <= m; i++) {  //存入
    int u, v, w;
    cin >> u >> v >> w;
    node[u][v] = min(node[u][v], w);
  }
  for (int i = 1; i <= n; i++) {  //自己指向自己的价值为0
    node[i][i] = 0;
  }
  for (int k = 1; k <= n; k++) {  //背下来即可
    for (int i = 1; i <= n; i++) {
      for (int j = 1; j <= n; j++) {
        node[i][j] = min(node[i][j], node[i][k] + node[k][j]);
      }
    }
  }
  while (q--) {
    int u, v;
    cin >> u >> v;
    cout << (node[u][v] >= 4e18 ? -1 : node[u][v]) << endl;
  }
}

signed main() {
  ios::sync_with_stdio(false), cin.tie(nullptr), cout.tie(nullptr);
  solve();
  return 0;
}