网站规划有哪些内容,淮南网络宾馆,wordpress 网站变慢,西安房产网58来源#xff1a;牛客网#xff1a; 文章目录题目描述题解#xff1a;代码#xff1a;时间限制#xff1a;C/C 1秒#xff0c;其他语言2秒
空间限制#xff1a;C/C 1048576K#xff0c;其他语言2097152K
64bit IO Format: %lld题目描述 给一个连通图#xff0c;每次询问…来源牛客网
文章目录题目描述题解代码时间限制C/C 1秒其他语言2秒
空间限制C/C 1048576K其他语言2097152K
64bit IO Format: %lld题目描述 给一个连通图每次询问两点间最短路。每条边的长度都是1。 输入描述: 第一行两个整数n和m表示图的点数和边数1≤ n≤ 100000, 1≤ m≤ n100。 接下来m行每行两个整数a和b表示一条边1≤ a, b≤ n。保证没有自环和重边。保证图连通。 接下来一个整数q表示询问的个数1≤ q≤ 100000。 接下来q行每行两个整数a和b表示询问a和b之间的最短路。 输出描述: 每个询问输出一行表示答案。 示例1 输入
4 5
1 2
2 3
1 4
4 3
2 4
4
1 4
1 2
2 4
1 3输出
1
1题解
我看了别人的讲解才逐渐明白。。我太菜了 题目是最短路题目内容也是最短路但是解法却不是常用的spfa等因为询问的个数有点多1 ~ 100000 我们仔细看数据范围mn100,什么意思想想m n-1时是一棵树那我们就可以把他当做树处理然后剩下的边再慢慢干 如果当做一棵树的话边长为1求最短路径我们就可以通过最近公共祖先lca得到两点的最近距离dep[a]dep[b] - 2dep [ lca(a, b) ] (a的深度b的深度然后a和b有重复的部分减去重复的部分) 然后我们看看多出来的100个边会对结果有什么影响 蓝色是原本的树橙色绿色是多出来的边 如果是橙色对结果没有影响如果是绿色会有影响 那么该如何处理 我们可以把剩下多出来的边跑单元最短路以这些边的一个端点开始并记录下来 然后与原路径进行比较 a到b的最小距离就在dep[a] dep[b]-2dep[ lca(a,b) ]与dis[a[i]]dis[b[i]]中取最小值 不知道有没有听明白我拿样例做个分析 我们看一下样例
1 2
2 3
1 4
4 3
2 4多余的边是1-2 , 4-3, ans最开始的值就是树上的lca ans{1,2,1,3} 然后开始跑1-2这个边从1这个点开始计算出1到个点的距离 dis{0,1,2,1} 然后更新最短距离 ans[i] min(ans[i], dis[a[i]] dis[b[i]]); a和b分别表示询问中a和b的距离 a[2]1,b[2]2 dis[a[2]]dis[b[2]]011ans[2] 所以ans[2]1 大致就是这个过程
代码
代码来自
#includebits/stdc.h
using namespace std;
#define fi first
#define se second
#define pb push_back
#define mp make_pair
#define all(x) (x).begin(), (x).end()
#define endl \n
#define SZ(x) (int)x.size()
typedef long long ll;
typedef pairint, int pii;
typedef pairll, ll pll;
const int mod 1e97;
//const int mod 998244353;
const double eps 1e-10;
const double pi acos(-1.0);
const int maxn 1e610;
const ll inf 0x3f3f3f3f;
const int dir[][2]{{0, 1}, {1, 0}, {0, -1}, {-1, 0}, {1, 1}, {1, -1}, {-1, 1}, {-1, -1}};
int n, m, depth[maxn], f[maxn][50];
int from[maxn], to[maxn 1], nxt[maxn 1], cnt 1, Log[maxn], From[maxn];
bool vis[maxn], used[maxn];
//链式前向星加边
void addEdge (int u, int v) {From[cnt] u, to[cnt] v, nxt[cnt] from[u], from[u] cnt;
}
//计算深度计算祖先
void dfs (int u, int fa) {depth[u] depth[fa] 1;vis[u] 1;for (register int i 1; i Log[n]; i) {if ((1 i) depth[u]) break;f[u][i] f[f[u][i - 1]][i - 1];}for (register int i from[u]; i; i nxt[i]) {ll v to[i];if (vis[v]) continue;used[i] used[i ^ 1] 1;f[v][0] u;dfs (v, u);}
}
//计算LCA
inline int LCA (int x, int y) {if (depth[x] depth[y]) swap(x, y);//我们默认x为更深的那个点for(register int i Log[n] ; i 0 ; --i)if(depth[x] - (1 i) depth[y]) x f[x][i];//将x跳到和y同一深度上if (x y) return x;for (register int i Log[n]; i 0; --i)if (f[x][i] ! f[y][i])x f[x][i], y f[y][i];//一起向上跳return f[x][0];//不难看出此时两个点均在其LCA的下方往上跳一次即可
}
void init(){Log[0] -1;for (register int i 1, u, v; i m; i) {cin u v;addEdge (u, v); addEdge(v, u);Log[i] Log[i 1] 1;}Log[n] Log[n 1] 1;dfs(1, 0);
}
int dist(int p , int q){return depth[p] depth[q] - 2 * depth[LCA(p , q)];}
int ans[maxn],a[maxn],b[maxn],dis[maxn], Q, q[maxn], h, t;
void bfs(int s){for (int i 1; i n; i)dis[i] inf;dis[s] 0;h t 0;q[h] s;while (t h) {int u q[t];for (int i from[u]; i; i nxt[i]){int v to[i];if (dis[v] dis[u] 1)dis[v] dis[u] 1, q[h] v;}}for (int i 1; i Q; i)ans[i] min(ans[i], dis[a[i]] dis[b[i]]);
}
int main()
{ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
// freopen(in.txt, r, stdin);
// freopen(out.txt, w, stdout);cin n m;init();cin Q;for (int i 1; i Q; i){cin a[i] b[i];ans[i] dist(a[i], b[i]);}int num 0;for (int i 2; i cnt; i)if(!used[i]) {used[i] used[i ^ 1] 1;bfs(From[i]);num;if(num 101) break;}for (int i 1; i Q; i)cout ans[i] endl;return 0;
}
