{"id":1009,"date":"2014-10-04T15:00:00","date_gmt":"2014-10-04T07:00:00","guid":{"rendered":"http:\/\/www.shuizilong.com\/house\/?p=1009"},"modified":"2014-10-04T15:54:53","modified_gmt":"2014-10-04T07:54:53","slug":"pku-campus-2011","status":"publish","type":"post","link":"https:\/\/www.shuizilong.com\/house\/archives\/pku-campus-2011\/","title":{"rendered":"PKU Campus 2011"},"content":{"rendered":"

<\/a>
\n<\/p>\n

Problem B. A Problem about Tree<\/p>\n

\u79bb\u7ebf + dfs()<\/p>\n

\r\nconst int N = int(1e4) + 9, M = int(1e4) + 9;\r\nint fa[N]; VI todo[N], adj[N]; int path[N];\r\nint n, m;\r\n\r\nint vis[N];\r\n\r\nstruct qry{\r\n    int u, r, z;\r\n    void in(){\r\n        z = -1;\r\n        scanf("%d %d", &u, &r);\r\n    }\r\n    void out(){\r\n        if (z == -1) z = fa[r];\r\n        printf("%d\\n", z);\r\n    }\r\n} Q[M];\r\n\r\n\r\nvoid dfs(int u = 1){\r\n\r\n    vis[u] = 1;\r\n\r\n    ECH(it, todo[u]){\r\n        int id = *it, r = Q[id].r;\r\n        Q[id].z = vis[r] == 1 ? path[r] : -1;\r\n    }\r\n\r\n\r\n    ECH(it, adj[u]){\r\n        int v = *it; if (v != fa[u]){\r\n            fa[v] = u;\r\n            path[u] = v;\r\n            dfs(v);\r\n        }\r\n    }\r\n\r\n    vis[u] = 0;\r\n}\r\n\r\n\r\n\r\nint main(){\r\n\r\n    \/\/freopen("e.txt", "r", stdin);\r\n\r\n    int T; cin >> T; while (T--){\r\n\r\n        cin >> n >> m;\r\n        REP_1(i, n) todo[i].clear(), adj[i].clear();\r\n\r\n        DO(n-1){\r\n            int a, b; scanf("%d %d", &a, &b);\r\n            adj[a].PB(b);\r\n            adj[b].PB(a);\r\n        }\r\n\r\n        REP(i, m){\r\n            Q[i].in();\r\n            todo[Q[i].u].PB(i);\r\n        }\r\n\r\n        dfs();\r\n        REP(i, m) Q[i].out();\r\n    }\r\n}\r\n\r\n<\/pre>\n
Dijkstra + Dp<\/p>\n
\r\nconst int N = int(5e2) + 9;\r\n\r\nvector<PII> adj[N]; int pre[N];\r\nint d[N][N];\r\nint n, m;\r\n\r\npriority_queue<PII, vector<PII>, greater<PII> > Q;\r\n\r\nvoid Dijkstra(int d[], int s){\r\n\r\n    fill(d, d+n, INF); d[s] = 0; Q.push(MP(0, s));\r\n\r\n    while (!Q.empty()){\r\n        int u = Q.top().se, du = Q.top().fi; Q.pop(); if (du != d[u]) continue;\r\n\r\n        ECH(it, adj[u]){\r\n            int v = it->fi, w = it->se;\r\n            if (d[v] > d[u] + w){\r\n                d[v] = d[u] + w;\r\n                Q.push(MP(d[v], v));\r\n            }\r\n        }\r\n    }\r\n}\r\n\r\nint dp[2][N][N];\r\n\r\nint main(){\r\n\r\n    \/\/freopen("in.txt", "r", stdin);\r\n\r\n    while (~scanf("%d %d", &n, &m)){\r\n        ++n; REP(i, n) adj[i].clear();\r\n\r\n        REP(i, m){\r\n            int a, b, c; scanf("%d %d %d", &a, &b, &c);\r\n            if (a == b) continue;\r\n            adj[a].push_back(make_pair(b, c)); swap(a,b);\r\n            adj[a].push_back(make_pair(b, c));\r\n        }\r\n\r\n        REP(i, n) Dijkstra(d[i], i);\r\n        int p = 0, q = 1; swap(p, q); FLC(dp[p], 0x3f); dp[p][0][0] = 0;\r\n\r\n        FOR(i, 1, n){\r\n            swap(p, q); int a = i-1; FLC(dp[p], 0x3f);\r\n#define u dp[q][b][c]\r\n            REP(b, n) REP(c, n) if (u != INF){\r\n                checkMin(dp[p][b][c], u + d[a][i]);\r\n                checkMin(dp[p][a][c], u + d[b][i]);\r\n                checkMin(dp[p][a][b], u + d[c][i]);\r\n            }\r\n        }\r\n\r\n        int z = INF; REP(i, n) REP(j, n) if (dp[p][i][j] != INF){\r\n            checkMin(z, dp[p][i][j] + d[n-1][0] + d[i][0] + d[j][0]);\r\n        }\r\n        cout << z << endl;\r\n    }\r\n}\r\n\r\n<\/pre>\n","protected":false},"excerpt":{"rendered":"","protected":false},"author":1,"featured_media":0,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"jetpack_post_was_ever_published":false,"_jetpack_newsletter_access":"","_jetpack_dont_email_post_to_subs":false,"_jetpack_newsletter_tier_id":0,"_jetpack_memberships_contains_paywalled_content":false,"_jetpack_memberships_contains_paid_content":false,"footnotes":"","jetpack_publicize_message":"","jetpack_publicize_feature_enabled":true,"jetpack_social_post_already_shared":true,"jetpack_social_options":{"image_generator_settings":{"template":"highway","enabled":false}}},"categories":[1],"tags":[],"class_list":["post-1009","post","type-post","status-publish","format-standard","hentry","category-uncategorized"],"jetpack_publicize_connections":[],"jetpack_featured_media_url":"","jetpack_shortlink":"https:\/\/wp.me\/p2tdP7-gh","jetpack_sharing_enabled":true,"_links":{"self":[{"href":"https:\/\/www.shuizilong.com\/house\/wp-json\/wp\/v2\/posts\/1009","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/www.shuizilong.com\/house\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/www.shuizilong.com\/house\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/www.shuizilong.com\/house\/wp-json\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"https:\/\/www.shuizilong.com\/house\/wp-json\/wp\/v2\/comments?post=1009"}],"version-history":[{"count":1,"href":"https:\/\/www.shuizilong.com\/house\/wp-json\/wp\/v2\/posts\/1009\/revisions"}],"predecessor-version":[{"id":1010,"href":"https:\/\/www.shuizilong.com\/house\/wp-json\/wp\/v2\/posts\/1009\/revisions\/1010"}],"wp:attachment":[{"href":"https:\/\/www.shuizilong.com\/house\/wp-json\/wp\/v2\/media?parent=1009"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/www.shuizilong.com\/house\/wp-json\/wp\/v2\/categories?post=1009"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/www.shuizilong.com\/house\/wp-json\/wp\/v2\/tags?post=1009"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}