Subtask 1

Duyệt mọi ngôi nhà ~u~ và tìm đường đi ngắn nhất tới các ngôi nhà còn lại, đáp án sẽ là khoảng cách ngắn nhất từ ~u~ tới ~p_i~ (~1 \le i \le k~).

Subtask 2

Sử dụng thuật toán Dijkstra đi từ các quán trà sữa tới mọi căn nhà còn lại, với ~d_i~ là đường đi ngắn nhất từ một quán trà sữa bất kì tới ~i~. Vì ~t_i = 0~ nên với những nhà tự mở quán thì ~d_i = 0~.

Subtask 3

Với điều kiện ràng buộc là cây, ta có thể quy hoạch động trên cây, với ~dp_{child}[u]~ là khoảng cách từ quán trà sữa gần nhất nào đó trong cây con gốc ~u~ tới ~u~, và ~dp_{par}[u]~ là khoảng cách từ quán trà sữa gần nhất nào đó phải đi qua ~par[u]~ tới ~u~.

Đáp án với mỗi đỉnh ~u~ sẽ là ~min(dp_{child}[u], dp_{par}[u])~.

Subtask 4

Cũng dựa vào Subtask 2 nhưng ta cần tìm quán trà sữa gần nhất cho các quán có ~t_i = 1~. Lúc này, ~d_i~ sẽ lưu ~2~ khoảng cách ngắn nhất từ ~2~ quán trà sữa khác nhau bất kì tới ~i~. Với những ngôi nhà có quán và ~t_i = 1~ thì đáp án sẽ là khoảng cách ngắn thứ ~2~ sau khoảng cách ngắn nhất bằng ~0~ do uống ở nhà.

#include <bits/stdc++.h>
#define ll long long
#define pa pair<ll, int>
#define fi first
#define se second
using namespace std;
const int N = 1e5+5;
const ll oo = 1e18;
int n, m, k;
vector<pa> adj[N];
bool milktea[N], findNew[N];
ll d[2][N];
int origin[2][N];
void Dijkstra() {
    priority_queue<pa, vector<pa>, greater<pa> > pq;
    for (int i = 1; i <= n; i++) {
        d[0][i] = d[1][i] = oo;
        if (milktea[i]) {
            d[0][i] = 0, origin[0][i] = i;
            pq.emplace(0, i);
        }
    }
    ll dist, tempDist;
    int node, root, far;
    while(!pq.empty()) {
        tie(dist, node) = pq.top(); pq.pop();
        if (node > n) far = 1, node -= n;
        else far = 0;

        if (dist != d[far][node]) continue;
        root = origin[far][node];
        for (auto x: adj[node]) {
            tempDist = dist + x.fi;
            if (!far && d[0][x.se] > tempDist) {
                if (origin[0][x.se] != root) {
                    origin[1][x.se] = origin[0][x.se];
                    d[1][x.se] = d[0][x.se];
                    pq.emplace(d[1][x.se], x.se + n);
                }
                origin[0][x.se] = root;
                d[0][x.se] = tempDist;
                pq.emplace(d[0][x.se], x.se);
            }
            else if (d[1][x.se] > tempDist && origin[0][x.se] != root) {
                origin[1][x.se] = root;
                d[1][x.se] = tempDist;
                pq.emplace(d[1][x.se], x.se + n);
            }
        }
    }
}
int main() {
    cin.tie(0) -> sync_with_stdio(0);
    freopen("milktea.inp", "r", stdin);
    freopen("milktea.out", "w", stdout);
    cin >> n >> m >> k;
    assert(2 <= k && k <= n);
    for (int i = 1, u, v, w; i <= m; i++) {
        cin >> u >> v >> w;
        adj[u].emplace_back(w, v);
        adj[v].emplace_back(w, u);
    }
    for (int i = 1, x; i <= k; i++) {
        cin >> x;
        milktea[x] = 1;
        cin >> findNew[x];
    }
    Dijkstra();
    for (int i = 1; i <= n; i++) {
        if (!milktea[i] || !findNew[i]) cout << d[0][i] << ' ';
        else cout << d[1][i] << ' ';
//        cerr << i << endl;
//        cerr << d[0][i] << ' ' << origin[0][i] << endl;
//        cerr << d[1][i] << ' ' << origin[1][i] << endl;
    }
    return 0;
}