題意

題目鏈接

題意：給出一張無向圖，每次詢問兩點之間的最短路，滿足$m - n <= 20$

$n, m, q \leqslant 10^5$

Sol

非常好的一道題。

首先建出一個dfs樹。

因為邊數-點數非常少，所以我們可以對于某些非樹邊特殊考慮。

具體做法是：對于非樹邊連接的兩個點，暴力求出它們到所有點的最短路

對于詢問的$(x, y)$

用樹上的邊，以及非樹邊連接的點到他們的最短路之和更新答案

由于邊數的限制，非樹邊連接的點不會超過$2*(m - (n - 1)) = 42$個

#include<bits/stdc++.h> #define Pair pair<int, int> #define MP(x, y) make_pair(x, y) #define fi first #define se second #define LL long long using namespace std; const int MAXN = 2 * 1e5 + 10; inline int read() {char c = getchar(); int x = 0, f = 1;while(c < '0' || c > '9') {if(c == '-') f = -1; c = getchar();}while(c >= '0' && c <= '9') x = x * 10 + c - '0', c = getchar();return x * f; } int N, M, Q, head[MAXN], num = 0, vis[MAXN], fa[MAXN][21], dep[MAXN], happen[MAXN]; LL dis[50][MAXN], Tdis[MAXN]; vector<int> p; struct Edge {LL u, v, w, f, nxt; }E[MAXN]; inline void AddEdge(int x, int y, int z) {E[num] = (Edge) {x, y, z, 0, head[x]};head[x] = num++; } void dfs(int x, int _fa) {vis[x] = 1; dep[x] = dep[_fa] + 1;for(int i = head[x]; ~i; i = E[i].nxt) {int to = E[i].v;if(vis[to]) continue;E[i].f = E[i ^ 1].f = 1;Tdis[to] = Tdis[x] + (LL)E[i].w;fa[to][0] = x;dfs(to, x);} } void Dij(int x, int id) {memset(dis[id], 0x7f, sizeof(dis[id])); dis[id][x] = 0;memset(vis, 0, sizeof(vis));priority_queue<Pair> q; q.push(MP(0, x));while(!q.empty()) {int p = q.top().se; q.pop();if(vis[p]) continue;for(int i = head[p]; ~i; i = E[i].nxt) {int to = E[i].v;if(dis[id][to] > dis[id][p] + E[i].w && (!vis[to])) dis[id][to] = dis[id][p] + E[i].w, q.push(MP(-dis[id][to], to));}} } void Pre() {for(int j = 1; j <= 20; j++)for(int i = 1; i <= N; i++)fa[i][j] = fa[fa[i][j - 1]][j - 1]; } int lca(int x, int y) {if(dep[x] < dep[y]) swap(x, y);for(int i = 20; i >= 0; i--)if(dep[fa[x][i]] >= dep[y]) x = fa[x][i];if(x == y) return x;for(int i = 20; i >= 0; i--)if(fa[x][i] != fa[y][i])x = fa[x][i], y = fa[y][i];return fa[x][0]; } main() { // freopen("a.in", "r", stdin);memset(head, -1, sizeof(head));N = read(); M = read();for(int i = 1; i <= M; i++) {int x = read(), y = read(), z = read();AddEdge(x, y, z);AddEdge(y, x, z);}dfs(1, 0);for(int i = 0; i < num; i++) if(!E[i].f) {if(!happen[E[i].u]) p.push_back(E[i].u), happen[E[i].u] = 1;if(!happen[E[i].v]) p.push_back(E[i].v), happen[E[i].v] = 1;}for(int i = 0; i < p.size(); i++) Dij(p[i], i);Pre();int Q = read();while(Q--) {int x = read(), y = read();LL ans = Tdis[x] + Tdis[y] - 2 * Tdis[lca(x, y)];for(int i = 0; i < p.size(); i++) ans = min(ans, dis[i][x] + dis[i][y]);cout << ans << endl;}return 0; }

轉載于:https://www.cnblogs.com/zwfymqz/p/9688315.html

總結

以上是生活随笔為你收集整理的cf1051F. The Shortest Statement(最短路)的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。