[CSP-S 2026] 地铁 / subway题解

思路

首先以把「线路」看成状态节点。定义：

• dp[i][j] = 从线路 i 的站台到线路 j 的站台所需的最小步行时间（只计换乘步行）。

1. 同站换乘边

同一地铁站u可能被多条线路经过。若线路i在站u的站台代价为 a，线路j在站u的站台代价为b,则从线路i换到线路j需要：a+b的代价 由于d<=20,n<=500很容易想到弗洛伊德,

2.回答询问

对于询问(x,y)

• 枚举枚举起点站x的所有线路i，枚举起点站y的所有线路j
  w[x]+c[x]+dp[i][j]+c[y]+w[y]

代码

#include
#define int long long
using namespace std;
const int N=510;
const int M=5e6+10;
int dp[N][N];
int c,n,m,d,q;
struct node{int v,w;};
vector e[M];
int w[M];
signed main(){cin >> c >> n >> m >> d >> q;for(int i=1;i<=m;i++) cin >> w[i];for(int i=1;i<=n;i++){int k;cin >> k;for(int j=1;j<=k;++j){int u,v;cin >> u >> v;e[u].push_back({i,v});}}memset(dp,0x3f,sizeof(dp));for(int i=1;i<=n;i++) dp[i][i]=0;for(int i=1;i<=m;i++){int l=e[i].size();for(int j=0;j> u >> v;int ans=1e18;int len1=e[u].size();int len2=e[v].size();for(int i=0;i