题解 CF1051F 【The Shortest Statement】

这道题思路比较有意思，第一次做完全没想到点子上。。。

看到题目第一反应是一道最短路裸题，但是数据范围1e5说明完全不可能。

这个时候可以观察到题目给出了一个很有意思的条件，就是说边最多比点多20。

这有什么用呢？

那么我们大胆猜想，可否将整个图划分为21条边（连接最多42个点）和一颗树？（极限情况）

如果这样的话，对于任意的两个节点uv，它们之间的最短路只有两种情况：

这两个点都在树上。所以说最短路必然是u->lca(u,v)->v。
不是上面那种情况。这个时候肯定会有连到外面那21个边。我们暴力枚举一下就可以了。

到这里思路就完全出来了，我们先把不属于树的点挑出来，对每一个都跑一下最短路。

然后对于每一组询问判断一下属于哪一种情况就可以了。

AC代码如下：

37657ms 67712kb

#include<iostream>

#include<cstdio>

#include<algorithm>

#include<cstring>

#include<queue>

using namespace std;

namespace StandardIO{

	template<typename T>inline void read(T &x){

		x=0;T f=1;char c=getchar();

		for(;c<'0'||c>'9';c=getchar())if(c=='-')f=-1;

		for(;c>='0'&&c<='9';c=getchar())x=x*10+c-'0';

		x*=f;

	}

	template<typename T>inline void write(T x){

		if(x<0)putchar('-'),x*=-1;

		if(x>=10)write(x/10);

		putchar(x%10+'0');

	}

}

using namespace StandardIO;

namespace Solve{

	#define int long long

	const int N=100100;

	const int INF=2147483647;

	int n,m,p;

	int cnt;

	int head[N];

	struct node{

		int to,val,next;

	}edge[N<<1];

	template<typename T>inline void add(T a,T b,T c){

		edge[++cnt].to=b,edge[cnt].val=c,edge[cnt].next=head[a],head[a]=cnt;

	}

	struct qnode{

		int key,val;

		bool operator < (qnode x)const{

			return val>x.val;

		}

	};

	int top;

	int vis[N],fa[N][23],dist[N],dep[N],q[N];

	int dis[50][N];

	inline void dfs(int now,int father){

		vis[now]=1,fa[now][0]=father;

		for(register int i=head[now];i;i=edge[i].next){

			int to=edge[i].to;

			if(to==father)continue;

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

			else{

				dep[to]=dep[now]+1,dist[to]=dist[now]+edge[i].val;

				dfs(to,now);

			}

		}

	}

	template<typename T>inline T lca(T x,T y){

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

		for(register int i=19;i>=0;--i){

			if(dep[fa[x][i]]>=dep[y])x=fa[x][i];

		}

		if(x==y)return x;

		for(register int i=19;i>=0;--i){

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

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

			}

		}

		return fa[x][0];

	}

	inline void dijkstra(int now){

		memset(dis[now],63,sizeof(dis[now]));

		memset(vis,0,sizeof(vis));

		priority_queue<qnode>Q;

		dis[now][q[now]]=0;

		Q.push((qnode){q[now],0});

		while(!Q.empty()){

			int tmp=Q.top().key;Q.pop();

			if(vis[tmp])continue;

			vis[tmp]=1;

			for(register int i=head[tmp];i;i=edge[i].next){

				int to=edge[i].to;

				if(!vis[to]&&dis[now][tmp]+edge[i].val<dis[now][to]){

					dis[now][to]=dis[now][tmp]+edge[i].val;

					Q.push((qnode){to,dis[now][to]});

				}

			}

		}

	}

	inline void solve(){

		read(n),read(m);

		for(register int i=1;i<=m;++i){

			int a,b,c;

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

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

		}

		dep[1]=1,dfs(1,0);

		for(register int j=1;j<=19;++j){

			for(register int i=1;i<=n;++i){

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

			}

		}

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

		for(register int i=1;i<=top;++i)dijkstra(i);

		read(p);

		while(p--){

			int x,y;

			read(x),read(y);

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

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

			write(ans),putchar('\n');

		}

	}

}

using namespace Solve;

#undef int

int main(){

	solve();

}

巴特西

题解 CF1051F 【The Shortest Statement】

最新文章

热门文章