题解：P17832 [CSP-S 2026] 地铁

lailai0916 · 2026-10-31 18:21:59 · 题解

解题思路

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

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

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

参考代码

#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;
}