正文

codeforces 1051F The Shortest Statement

IP云
IP云V管理员/3 阅读
10/01
提示：扫一扫查出行
【扫一扫了解最新限行尾号】
复制提示

题目链接：codeforces 1051F The Shortest Statement

题意：\(q\)组询问，求任意两点之间的最短路，图满足\(m-n\leq 20\)

分析：一开始看这道题：floyd?简单

​ 看下去：\(n\leq 10^5\)，有点可怕

​ 接下去：\(q\leq 10^5\)，mmp

题目中十分重要的条件是\(m-n\leq 20\)，我们要考虑如何利用好它使得能在\(O(logn)\)左右的时间内求出两点间最短路

由于\(m\)和\(n\)相差不大，我们很容易想到一种特殊的图——树，它保证\(m-n=-1\)

在树上求两点之间的最短路是比较容易的：记树上点\(u\)到根节点距离为\(dis(u)\)，那么任意两点\((u,v)\)距离就是\(dis(u)+dis(v)-2*dis(lca(u,v))\)

那么我们可以考虑将原来图通过删边转化成一棵树，那么由于条件我们知道我们最多删去21条边，由于每条边都有两个端点，所以最多会影响的点为42个

我们的最短路也可以被分为两种：只走树边或会走非树边，只走树边的话我们直接用上面方法求解，走非树边的话，那么就一定会经过那42个点中的一部分，我们可以将\(u,v\)之间的最短路表示成\(dis(x,u)+dis(x,v)\)（\(x\)属于那42个点）。那么我们可以预处理出那42个点到图中的所有点的最短路，然后枚举这42个点求出最短路

最后对于所有算出的距离取\(min\)即可

#include<iostream>
#include<string.h>
#include<string>
#include<stdio.h>
#include<algorithm>
#include<vector>
#include<queue>
#include<map>
using namespace std;
const long long maxd=1e18+7;
struct node{
int to,nxt;
long long cost;
}sq[200500];struct hnode{
int u;long long dis;
bool operator <(const hnode &p)const{
return dis>p.dis;
}
};int n,m,q,head[100500],fa[100500][25],low[100500],
dep[100500],all=0,point[200100],cnt=0;
long long dis[50][100500],d[200500];
bool vis[100100];int read()
{
int x=0,f=1;char ch=getchar();
while ((ch<'0') || (ch>'9')) {if (ch=='-') f=-1;ch=getchar();}
while ((ch>='0') && (ch<='9')) {x=x*10+(ch-'0');ch=getchar();}
return x*f;
}void add(int u,int v,long long w)
{
all++;sq[all].to=v;sq[all].nxt=head[u];sq[all].cost=w;head[u]=all;
}void dfs(int u,int fu)
{
vis[u]=1;dep[u]=dep[fu]+1;fa[u][0]=fu;
int i;
for (i=1;i<=low[dep[u]];i++)
fa[u][i]=fa[fa[u][i-1]][i-1];
for (i=head[u];i;i=sq[i].nxt)
{
int v=sq[i].to;
if (v==fu) continue;
if (vis[v]) {point[++cnt]=u;point[++cnt]=v;}
else
{
d[v]=d[u]+sq[i].cost;
dfs(v,u);
}
}
}void dij(int id)
{
int i;
for (i=1;i<=n;i++) dis[id][i]=maxd;
memset(vis,0,sizeof(vis));
dis[id][point[id]]=0;
priority_queue<hnode> q;
q.push((hnode){point[id],0});
while (!q.empty())
{
hnode now=q.top();q.pop();
int u=now.u;
if (vis[u]) continue;vis[u]=1;
for (i=head[u];i;i=sq[i].nxt)
{
int v=sq[i].to;
if ((dis[id][v]>dis[id][u]+sq[i].cost))
{
dis[id][v]=dis[id][u]+sq[i].cost;
q.push((hnode){v,dis[id][v]});
}
}
}
}int LCA(int u,int v)
{
if (dep[u]<dep[v]) swap(u,v);
while (dep[u]>dep[v]) u=fa[u][low[dep[u]-dep[v]]];
if (u==v) return u;
int i;
for (i=low[dep[u]];i>=0;i--)
if (fa[u][i]!=fa[v][i]) {u=fa[u][i];v=fa[v][i];}
return fa[u][0];
}int main()
{
n=read();m=read();
memset(head,0,sizeof(head));
memset(vis,0,sizeof(vis));
memset(d,0,sizeof(d));
int i;
for (i=1;i<=m;i++)
{
int u=read(),v=read(),w=read();
add(u,v,w);add(v,u,w);
}
low[1]=0;dep[0]=0;
for (i=2;i<=n;i++) low[i]=low[i>>1]+1;
dfs(1,0);
sort(point+1,point+1+cnt);
cnt=unique(point+1,point+1+cnt)-point-1;
for (i=1;i<=cnt;i++) dij(i);
q=read();
//for (i=1;i<=n;i++) cout << dep[i] << " ";cout << endl;
while (q--)
{
int u=read(),v=read();
long long ans=d[u]+d[v]-2*d[LCA(u,v)];
for (i=1;i<=cnt;i++) ans=min(ans,dis[i][u]+dis[i][v]);
printf("%I64d\n",ans);
}
return 0;
}
/*
3 3
1 2 3
2 3 1
3 1 5
3
1 2
1 3
2 3
*/