解题思路

同一线路乘车代价为 $0$，将每条线路缩成一点。设 $S_v$ 为经过站点 $v$ 的线路集合，$b_{i,v}$ 为该站站厅与线路 $i$ 站台间的步行时间。不同线路 $i,j$ 间边权为：

$$\min_{v:i,j\in S_v}(b_{i,v}+b_{j,v})$$

每条边均可在相应公共站点实现换乘，线路内移动免费，故图上最短路等于最小换乘代价。用 Floyd 求出最短路 $f_{i,j}$ 后，询问 $(x,y)$ 的答案为：

$$w_x+w_y+\min_{i\in S_x,j\in S_y}(b_{i,x}+f_{i,j}+b_{j,y})$$

每个站点至多经过 $d$ 条线路，查询仅需枚举首末线路。记 $K=\sum_{i=1}^n k_i$，总时间复杂度 $O(Kd+n^3+qd^2)$。

参考代码

895 Bcpp

#include <bits/stdc++.h>
using namespace std;

using ll=long long;
const int N=505;
const int M=500005;
const ll inf=0x3f3f3f3f3f3f3f3f;
ll dis[N][N];
int w[M];
vector<pair<int,int>> G[M];
int main()
{
	ios::sync_with_stdio(false);
	cin.tie(nullptr);
	int c,n,m,d,q;
	cin>>c>>n>>m>>d>>q;
	for(int i=1;i<=m;i++)cin>>w[i];
	memset(dis,0x3f,sizeof dis);
	for(int i=1;i<=n;i++)dis[i][i]=0;
	for(int i=1;i<=n;i++)
	{
		int k;
		cin>>k;
		for(int j=1;j<=k;j++)
		{
			int a,t;
			cin>>a>>t;
			for(auto [v,s]:G[a])dis[i][v]=dis[v][i]=min(dis[i][v],1ll*t+s);
			G[a].push_back({i,t});
		}
	}
	for(int k=1;k<=n;k++)
	{
		for(int i=1;i<=n;i++)
		{
			for(int j=1;j<=n;j++)dis[i][j]=min(dis[i][j],dis[i][k]+dis[k][j]);
		}
	}
	while(q--)
	{
		int x,y;
		cin>>x>>y;
		ll ans=inf;
		for(auto [u,s]:G[x])
		{
			for(auto [v,t]:G[y])ans=min(ans,s+dis[u][v]+t);
		}
		cout<<ans+w[x]+w[y]<<'\n';
	}
	return 0;
}