Баобаб

#include <vector>
#include <iostream>
#include <algorithm>

using namespace std;

int n;
vector<int> color(n + 1, 0);
vector<int> h(n + 1, 0);
vector<int> deep(n + 1, 0);
vector<vector<pair<int, int>>> vec(n + 1);

void dfs(int colour, int u, int v, int weight) {
    if (u == n) return;

    color[u] = colour;
    deep[u] = deep[v] + weight;

    if (color[vec[u][0].first] == 0) {
        dfs(colour, vec[u][0].first, u, vec[u][0].second);
        h[v] = h[vec[u][0].first] + vec[u][0].second;
    }
    if (color[vec[u][1].first] == 0) {
        dfs(colour, vec[u][1].first, u, vec[u][1].second);
        h[u] = h[vec[u][1].first] + vec[u][1].second;
    }

}



int main() {
    int m, q;
    int x, y;
    int u, v, c;
    cin >> n >> m >> q;

    vector<int> maxx(q, 1000000);

    vec.resize(n + 1);
    color.resize(n + 1, 0);
    h.resize(n + 1, 0);
    deep.resize(n + 1, 0);
    color[1] = 10000000;

    h[1] = 10000000;


    for (int i = 0; i < m; i++) {
        cin >> u >> v >> c;
        vec[u].push_back(make_pair(v, c));
        vec[v].push_back(make_pair(u, c));
    }

    for (int i = 0; i < vec[1].size(); i++) {
        dfs(i + 1, vec[1][i].first, 1, vec[1][i].second);
        h[1] = min(h[1], h[vec[1][i].first] + vec[1][i].second);
    }
    deep[n] = h[1];
    color[n] = 10000000;

    int minxy;

    for (int i = 0; i < q; i++) {
        cin >> x >> y;

        if (color[x] == color[y]) {
            minxy = abs(deep[x] - deep[y]);
            maxx[i] = min(maxx[i], minxy);
        }
        else {
            minxy = h[y] + h[x];
            maxx[i] = min(maxx[i], minxy);

            minxy = deep[y] + deep[x];
            maxx[i] = min(maxx[i], minxy);
        }

        minxy = h[1] + h[x] + deep[y];
        maxx[i] = min(maxx[i], minxy);

        minxy = h[1] + h[y] + deep[x];
        maxx[i] = min(maxx[i], minxy);

        minxy = h[1] + deep[x] + h[y];
        maxx[i] = min(maxx[i], minxy);

        minxy = h[1] + deep[y] + h[x];
        maxx[i] = min(maxx[i], minxy);

    }

    for (int i : maxx) {
        cout << i << ' ';
    }
    return 0;
}