[CF1051F]The Shortest Statement

题目大意：给定一张$n$个点$m$条有权边的无向联通图，$q$次询问两点间的最短路

$n\le100000$,$m\le100000$,$1\le100000$,$m$-$n\le20$.

首先看到$m$-$n\le20$这条限制，我们可以想到是围绕这个20来做这道题。

即如果我们随便在图上找一棵树，有最多21条非树边，连接最多42个顶点

考虑两点$x,y$之间的最短路就是某个点到$x$和$y$的最短路之和

首先对于只走树边的情况，这个点是两点的$LCA$

如果经过非树边，$x$或$y$到枚举的这个点的最短路上的最后一条边一定是非树边(如果都是树边的话完全可以转化到一个连接着非树边的点上去)

然后对于所有连接非树边的点都跑一遍最短路，询问时直接枚举这些点取$min$即可

代码：

 #include<iostream>

 #include<cstdio>

 #include<cstring>

 #include<queue>

 #include<algorithm>

 #define M 200010

 #define int long long

 using namespace std;

 int read()

 {

     char ch=getchar();int x=;

     while(ch>''||ch<'') ch=getchar();

     while(ch<=''&&ch>='') x=x*+ch-'',ch=getchar();

     return x;

 }

 struct point{

     int to,next,dis;

 }e[M<<];

 int n,m,num,Q,top;

 int q[M],head[M],deep[M],dist[M];

 int dis[][M],fa[M][];

 bool vis[M];

 struct node{int id,dis;};

 bool operator < (node a1,node a2) {return a1.dis>a2.dis;}

 void add(int from,int to,int dis)

 {

     e[++num].next=head[from];

     e[num].to=to;

     e[num].dis=dis;

     head[from]=num;

 }

 void dfs(int x,int f)

 {

     vis[x]=true; fa[x][]=f;

     for(int i=head[x];i;i=e[i].next)

     {

         int to=e[i].to;

         if(to==f) continue;

         if(vis[to]) q[++top]=x,q[++top]=to;

         else

         {

             deep[to]=deep[x]+;

             dist[to]=dist[x]+e[i].dis;

             dfs(to,x);

         }

     }

 }

 int lca(int x,int y)

 {

     if(deep[x]<deep[y]) swap(x,y);

     for(int i=;i>=;i--)

         if(deep[fa[x][i]]>=deep[y])

             x=fa[x][i];

     if(x==y) return x;

     for(int i=;i>=;i--)

         if(fa[x][i]!=fa[y][i])

             x=fa[x][i],y=fa[y][i];

     return fa[x][];

 }

 void Dijkstra(int id)

 {

     memset(dis[id],,sizeof(dis[id]));

     memset(vis,false,sizeof(vis));

     priority_queue<node>Q;

     dis[id][q[id]]=;

     Q.push((node){q[id],});

     while(!Q.empty())

     {

         int x=Q.top().id;Q.pop();

         if(vis[x]) continue;

         vis[x]=true;

         for(int i=head[x];i;i=e[i].next)

         {

             int to=e[i].to;

             if(!vis[to]&&dis[id][x]+e[i].dis<dis[id][to])

             {

                 dis[id][to]=dis[id][x]+e[i].dis;

                 Q.push((node){to,dis[id][to]});

             }

         }

     }

 }

 #undef int

 int main()

 {

     #define int long long

     n=read(); m=read();

     for(int i=;i<=m;i++)

     {

         int a=read(),b=read(),c=read();

         add(a,b,c); add(b,a,c);

     }

     deep[]=;dfs(,);

     for(int j=;j<=;j++)

         for(int i=;i<=n;i++)

             fa[i][j]=fa[fa[i][j-]][j-];

     sort(q+,q++top); top=unique(q+,q++top)-q-;

     for(int i=;i<=top;i++) Dijkstra(i);

     Q=read();

     while(Q--)

     {

         int x=read(),y=read();

         int ans=dist[x]+dist[y]-*dist[lca(x,y)];

         for(int i=;i<=top;i++) ans=min(ans,dis[i][x]+dis[i][y]);

         printf("%lld\n",ans);

     }

     return ;

 }

巴特西

[CF1051F]The Shortest Statement

最新文章

热门文章