题解 T93336 【最短路】

传送门

30%的做法

• floyd预处理出每两点间的最短路,每次询问$O(1)$回答

• 复杂度$O(n^3+q)$

---

另外20%的做法

• 树的情况

• 对于$u,v$的最短路，求出他们的LCA为$k$，$ans=d[u]+d[v]-2*d[k]$

• 可以用tarjan算法离线求LCA，那么总复杂度$O(n+q)$

• 也可以倍增 / 转化为RMQ在线求，复杂度$O(n+q \log n)$ / $O(n \log n+q)$

---

100%的做法

• $M<=N+20$，因此考虑沿用树的做法

• 我们可以从任一点为根开始，将整个图当成树做一个dfs（随便取一棵生成树）

• 那么整个图就是在这棵生成树$T$的基础上，多加了最多21条边。

• 考虑两个点的最短路，有两种情况：

• • 1.不经过这多出来的21条边，那么可以用树的方法在$O(1)$或者$O(\log n)$的做法求出
• • 2.经过这多出来的21条边。这种情况如何处理？

• 21条多出来的边最多涉及到42个图中的点，如果最短路经过这21条多出的边，那么一定经过这些点之一。

• 我们可以预处理出多出来的边涉及到的点为源点，到其它各点的最短路。

• 那么对于第2种情况，我们只需要枚举这些点作为中转点，取$\min$即可。两种情况取一个$\min$，即为他们实际的最短路。

• 例：设多出来的边涉及到的点为$k_1,k_2,..k_s$，我们要求$u,v$间的最短路。先求生成树T中他们间的路径长度，然后分别尝试以$k_1,k_2…k_s$中转的最短路，对这$s+1$个值取$\min$

• 单源最短路用dijkstra算法求出

• 复杂度$O(n \log n+q)$

// luogu-judger-enable-o2
#include <cstdio>
#include <iostream>
#include <vector>
#include <algorithm>
#include <queue>

#define pb push_back
#define mp make_pair
#define N 100005

using namespace std;

typedef pair<long long,int> pa;

vector<int> G[N], C[N];
vector<int> G1[N], C1[N];

int p[100], pcnt;
long long dist[100][N], d[N];
int n, m, q, fa[N];
int f[N][18], dep[N];
bool index[N];

int find(int x)
{
    return x==fa[x]?x:fa[x]=find(fa[x]);
}

int lca(int u, int v)
{
	if(dep[u]!=dep[v])
	{
		if(dep[u]<dep[v]) swap(u,v);
		for(int i=0,k=dep[u]-dep[v];k;i++)
		{
			if(k&1) u=f[u][i];
			k>>=1;
		}
	}
	if(u==v) return u;
	for(int i=17;i>=0;i--)
		if(f[u][i]!=f[v][i]) u=f[u][i],v=f[v][i];
	return f[u][0];
}

void dfs(int u,int fa)
{
	dep[u]=dep[fa]+1,f[u][0]=fa;
	for(int i=0;i<G[u].size();i++)
	{
		int v=G[u][i],di=C[u][i];
		if(v==fa)
		    continue;
		d[v]=d[u]+di;
		dfs(v,u);
	}
}

void dijkstra(int k)
{
	static bool ok[N];
	int s=p[k];
	for(int i=1;i<=n;i++)
	{
	    dist[k][i]=1e18;
	    ok[i]=0;
	}
	dist[k][s]=0;
	priority_queue<pa,vector<pa>,greater<pa> > pq;
	pq.push(mp(0ll,s));
	while(!pq.empty())
	{
		int u=pq.top().second; pq.pop();
		ok[u]=1;
		for(int i=0;i<G1[u].size();i++)
		{
			int v=G1[u][i],d=C1[u][i];
			if(!ok[v]&&dist[k][u]+d<dist[k][v])
			{
				dist[k][v]=dist[k][u]+d;
				pq.push(mp(dist[k][v],v));
			}
		}
	}
}

int main()
{
	scanf("%d%d%d",&n,&m,&q);
	for(int i=1;i<=n;i++)
	    fa[i]=i;
	for(int i=1,u,v,d;i<=m;i++)
	{
		scanf("%d%d%d",&u,&v,&d);
		G1[u].pb(v), C1[u].pb(d);
		G1[v].pb(u), C1[v].pb(d);
		if(find(u)!=find(v))
		{
			fa[find(u)]=find(v);
			G[u].pb(v),C[u].pb(d);
			G[v].pb(u),C[v].pb(d);
		}
		else
		    index[u]=index[v]=1;
	}
	for(int i=1;i<=n;i++)
		if(index[i])
		{
			p[++pcnt]=i;
			dijkstra(pcnt);
		}
	dfs(1,0);
	for(int j=1;j<=17;j++)
		for(int i=1;i<=n;i++)
		    f[i][j]=f[f[i][j-1]][j-1];
	for(int i=1,u,v;i<=q;i++)
	{
		scanf("%d%d",&u,&v);
		long long ans=d[u]+d[v]-d[lca(u,v)]*2;
		for(int i=1;i<=pcnt;i++)
			ans=min(ans,dist[i][u]+dist[i][v]);
		printf("%lld\n",ans);
	}
	return 0;
}