Problem B. A Problem about Tree

離線 + dfs()

const int N = int(1e4) + 9, M = int(1e4) + 9; int fa[N]; VI todo[N], adj[N]; int path[N]; int n, m; int vis[N]; struct qry{ int u, r, z; void in(){ z = -1; scanf("%d %d", &u, &r); } void out(){ if (z == -1) z = fa[r]; printf("%d\n", z); } } Q[M]; void dfs(int u = 1){ vis[u] = 1; ECH(it, todo[u]){ int id = *it, r = Q[id].r; Q[id].z = vis[r] == 1 ? path[r] : -1; } ECH(it, adj[u]){ int v = *it; if (v != fa[u]){ fa[v] = u; path[u] = v; dfs(v); } } vis[u] = 0; } int main(){ //freopen("e.txt", "r", stdin); int T; cin >> T; while (T--){ cin >> n >> m; REP_1(i, n) todo[i].clear(), adj[i].clear(); DO(n-1){ int a, b; scanf("%d %d", &a, &b); adj[a].PB(b); adj[b].PB(a); } REP(i, m){ Q[i].in(); todo[Q[i].u].PB(i); } dfs(); REP(i, m) Q[i].out(); } }

Dijkstra + Dp

const int N = int(5e2) + 9; vector<PII> adj[N]; int pre[N]; int d[N][N]; int n, m; priority_queue<PII, vector<PII>, greater<PII> > Q; void Dijkstra(int d[], int s){ fill(d, d+n, INF); d[s] = 0; Q.push(MP(0, s)); while (!Q.empty()){ int u = Q.top().se, du = Q.top().fi; Q.pop(); if (du != d[u]) continue; ECH(it, adj[u]){ int v = it->fi, w = it->se; if (d[v] > d[u] + w){ d[v] = d[u] + w; Q.push(MP(d[v], v)); } } } } int dp[2][N][N]; int main(){ //freopen("in.txt", "r", stdin); while (~scanf("%d %d", &n, &m)){ ++n; REP(i, n) adj[i].clear(); REP(i, m){ int a, b, c; scanf("%d %d %d", &a, &b, &c); if (a == b) continue; adj[a].push_back(make_pair(b, c)); swap(a,b); adj[a].push_back(make_pair(b, c)); } REP(i, n) Dijkstra(d[i], i); int p = 0, q = 1; swap(p, q); FLC(dp[p], 0x3f); dp[p][0][0] = 0; FOR(i, 1, n){ swap(p, q); int a = i-1; FLC(dp[p], 0x3f); #define u dp[q][b] REP(b, n) REP(c, n) if (u != INF){ checkMin(dp[p][b], u + d[a][i]); checkMin(dp[p][a], u + d[b][i]); checkMin(dp[p][a][b], u + d[i]); } } int z = INF; REP(i, n) REP(j, n) if (dp[p][i][j] != INF){ checkMin(z, dp[p][i][j] + d[n-1][0] + d[i][0] + d[j][0]); } cout << z << endl; } }