Дейкстра

#include <bits/stdc++.h>
using namespace std;

typedef long long ll;
typedef unsigned long long ull;

#define endl "\n"
#define ff first
#define ss second
#define int ll
#define fori(n) for (int i = 0; i < (n); i++)
#define forj(n) for (int j = 0; j < (n); j++)

//#pragma comment(linker, "/STACK:20000000000")
//#pragma GCC optimize("O3")
//#pragma GCC optimize("Ofast")
//#pragma GCC optimize("unroll-loops")

inline void boostIO() {
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    cout.precision(10);
}

inline int getint() {
    int val = 0;
    char c;
    while ((c = getchar()) && !(c >= '0' && c <= '9'));
    do {
        val = (val * 10) + c - '0';
    } while ((c = getchar()) && (c >= '0' && c <= '9'));
    return val;
}
inline int safe_mul(int x, int y, int mod) {
    return x * 1LL * y % mod;
}

inline void safe_add(int& x, int y, int mod) {
    x += y;
    if (x >= mod)
        x -= mod;
}

const int INF = 1e17;
const int modulo = 1e9 + 7;
const double EPS = 1e-7;
const double pi = 3.14159265358979323846;

const int maxn = 2e5 + 500;

vector<vector<int>> G;
vector<int> W[maxn];
vector<int> used;
vector<int> pr;
int flag = 0;

int Len[maxn]{INF};
set<pair<int,int>> Set;

void dijcstra(int n, int st){
    Len[st] = 0;
    Set.insert(make_pair(0, st));
    vector<int> prev(n, -1);
    while (!Set.empty()) {
        pair<int, int> p = *Set.begin();
        int v = p.second;
        Set.erase(Set.begin());
        for (int i = 0; i < G[v].size(); ++i) {
            int to = G[v][i];
            if (Len[v] + W[v][i] < Len[to]) {
                if (Len[to] != INF) {
                    auto it = Set.find(make_pair(Len[to], to));
                    Set.erase(it);
                }
                prev[to] = v;
                Len[to] = Len[v] + W[v][i];
                Set.insert(make_pair(Len[to], to));
            }
        }
    }
}

int32_t main() {
    int n;
    cin >> n;
    G.assign(n, vector<int>());
    used.assign(n, 0);
    pr.assign(n, -1);
    fori(n - 1){
        int u, v;
        cin >> u >> v;
        --u; --v;
        G[u].push_back(v);
    }

    return 0;
}