上海餐饮网站建设,2345网址导航设置,广西省住房和城乡建设厅网站,网站伪静态作用bzoj#2125. 最短路
题目描述 Description 给一个N个点M条边的连通无向图#xff0c;满足每条边最多属于一个环#xff0c;有Q组询问#xff0c;每次询问两点之间的最短路径。 Input 输入的第一行包含三个整数#xff0c;分别表示N和M和Q 下接M行#xff0c;每行三个整数v…bzoj#2125. 最短路
题目描述 Description 给一个N个点M条边的连通无向图满足每条边最多属于一个环有Q组询问每次询问两点之间的最短路径。 Input 输入的第一行包含三个整数分别表示N和M和Q 下接M行每行三个整数vuw表示一条无向边v-u长度为w 最后Q行每行两个整数vu表示一组询问 Output 输出Q行每行一个整数表示询问的答案 Solution
题意就是求仙人掌中两点最短路。
就是仙人掌圆方树的板子题。
对于每一个环用一个方点ttt代替环从方点ttt向这个环的根节点xxx连一条代价为000的边再从ttt向环上其他所有点yyy连一条代价为mindis(x,y)mindis(x,y)mindis(x,y)的边并在ttt上记录整个环的总长度sumtsum_tsumt。
每一次询问(x,y)(x,y)(x,y)最短路时分类讨论LCA(x,y)LCA(x,y)LCA(x,y)是方点还是圆点。 若是圆点答案即为dist(x,y)dist(x,y)dist(x,y)。 若是方点则答案为xxx到环的最短路yyy到环的最短路xxx接入环的节点与yyy接入环的节点之间的最短路。
因此只要倍增或树剖预处理出LCA与路径和每次跳LCA的时候顺路求解答案即可。
时间复杂度O(nlgn)O(n\lg n)O(nlgn)
#include vector
#include list
#include map
#include set
#include deque
#include queue
#include stack
#include bitset
#include algorithm
#include functional
#include numeric
#include utility
#include sstream
#include iostream
#include iomanip
#include cstdio
#include cmath
#include cstdlib
#include cctype
#include string
#include cstring
#include ctime
#include cassert
#include string.h
//#include unordered_set
//#include unordered_map
//#include bits/stdc.h#define MP(A,B) make_pair(A,B)
#define PB(A) push_back(A)
#define SIZE(A) ((int)A.size())
#define LEN(A) ((int)A.length())
#define FOR(i,a,b) for(int i(a);i(b);i)
#define fi first
#define se secondusing namespace std;templatetypename Tinline bool upmin(T x,T y) { return yx?xy,1:0; }
templatetypename Tinline bool upmax(T x,T y) { return xy?xy,1:0; }typedef long long ll;
typedef unsigned long long ull;
typedef long double lod;
typedef pairint,int PR;
typedef vectorint VI;const lod eps1e-11;
const lod piacos(-1);
const int oo130;
const ll loo1ll62;
const int mods1e97;
const int MAXN30005;
const int INF0x3f3f3f3f;//1061109567
/*--------------------------------------------------------------------*/
inline int read()
{int f1,x0; char cgetchar();while (c0||c9) { if (c-) f-1; cgetchar(); }while (c0c9) { x(x3)(x1)(c^48); cgetchar(); }return x*f;
}
struct enode{int to,c; };
vectorenode e[MAXN],E[MAXN];
int DFN0,n,m,Case,num,dist[MAXN],sum[MAXN],Fa[MAXN],flag[MAXN];
int dfn[MAXN],low[MAXN],fa[MAXN][15],sm[MAXN][15],dep[MAXN],Log[MAXN];
void add_edge(int x,int y,int c)
{
// coutEdge:x y cendl;E[x].PB(((enode){y,c}));E[y].PB(((enode){x,c}));
}
void solve(int x,int y,int c)
{sum[num]dist[y]-dist[x]c;add_edge(x,num,0);for (int py;p!x;pFa[p]){int Dismin(dist[p]-dist[x],sum[num]-(dist[p]-dist[x]));add_edge(p,num,Dis);flag[p](Dis(dist[p]-dist[x]));}
}
void tarjan(int x,int father)
{dfn[x]low[x]DFN,Fa[x]father;for (auto V:e[x]){int vV.to,cV.c;if (!dfn[v]) dist[v]dist[x]c,tarjan(v,x),upmin(low[x],low[v]);else if (v!father) upmin(low[x],dfn[v]);if (dfn[x]low[v]) add_edge(x,v,c);}for (auto V:e[x]){int vV.to,cV.c;if (Fa[v]!xdfn[v]dfn[x]) solve(x,v,c);}
}
void dfs(int x,int father)
{dep[x]dep[father]1;for (int i1;iLog[dep[x]];i) fa[x][i]fa[fa[x][i-1]][i-1],sm[x][i]sm[fa[x][i-1]][i-1]sm[x][i-1];for (auto v:E[x]){if (v.tofather) continue;fa[v.to][0]x;sm[v.to][0]v.c;dfs(v.to,x);}
}
int getans(int x,int y)
{int s0;if (dep[x]dep[y]) swap(x,y);for (int iLog[dep[x]];i0;i--)if (dep[fa[x][i]]dep[y]) ssm[x][i],xfa[x][i];
// coutx y fa[x][0] sendl;if (xy) return s;for (int iLog[dep[x]];i0;i--)if (fa[x][i]!fa[y][i]) ssm[x][i]sm[y][i],xfa[x][i],yfa[y][i];// coutx y fa[x][0] sendl;if (fa[x][0]n) return ssm[x][0]sm[y][0];int Dis;if (flag[x]^flag[y]) Dissm[x][0]sm[y][0];else Disabs(sm[x][0]-sm[y][0]);return smin(Dis,sum[fa[x][0]]-Dis);
}
int main()
{nread(),mread(),Caseread(),numn;for (int i1;im;i){int uread(),vread(),cread();e[u].PB(((enode){v,c}));e[v].PB(((enode){u,c}));}tarjan(1,0);dep[0]-1,Log[1]0;for (int i2;inum;i) Log[i]Log[i1]1;dfs(1,0);
// for (int i1;inum;i) coutfa[i][0] sm[i][0] fa[i][1] sm[i][1]endl;while (Case--){int xread(),yread();printf(%d\n,getans(x,y));}return 0;
}
/*
9 10 2
1 2 1
1 4 1
3 4 1
2 3 1
3 7 1
7 8 2
7 9 2
1 5 3
1 6 4
5 6 1
1 9
5 75
6
*/
