地铁

建模与算法

乘车时间不计入步行时间，所以同一线路的站台可以免费到达。把每条线路压成一个点。对同一站厅相交的线路i,j，换乘边权为t[i,v]+t[j,v]，多站相交取最小边。换乘不出地铁口，不额外加w[v]。

对至多500个线路点运行Floyd。对于起终站x,y，枚举经过x的线路i及经过y的线路j，答案为w[x]+t[i,x]+dist[i,j]+t[j,y]+w[y]。

正确性

任意真实出行都对应线路图上一条线路序列，其每次换乘代价不小于所选边的最小权，因此线路最短路给出下界。反过来，每条最短路边都能在实现该最小代价的交汇站换乘，同一线路上任意站台之间免费乘车，故这一代价可实现。起终点枚举覆盖所有选择，两边界相等。

时间O(n^3+Σ站点度数平方+q*d^2)，空间O(n^2+Σk_i+m)。使用64位，不能把最短路建在50万个站厅上逐次跑10万次Dijkstra。独立小规模oracle另建站厅—线路二部图，逐查询Dijkstra核对。

难度依据

6 / geekpi-9-v2：将站台的免费乘车压缩为线路图，Floyd预处理换乘代价，再枚举起终站所在线路。

参考程序

#include <cstdio>
#include <vector>
#include <algorithm>
#include <utility>
using namespace std;
struct Fast{static const int Z=1<<20;char b[Z];int p=0,n=0;char get(){if(p==n){n=fread(b,1,Z,stdin);p=0;if(!n)return 0;}return b[p++];}long long read(){char c;do c=get();while(c&&c<=32);long long x=0;while(c>='0'&&c<='9'){x=x*10+c-'0';c=get();}return x;}}in;
int main(){in.read();int n=in.read(),m=in.read();in.read();int q=in.read();vector<long long>w(m);for(auto&v:w)v=in.read();vector<vector<pair<int,int>>>s(m);for(int i=0;i<n;i++){int k=in.read();while(k--){int v=in.read()-1,t=in.read();s[v].push_back({i,t});}}const long long INF=4000000000000000000LL;vector<long long>d(n*n,INF);for(int i=0;i<n;i++)d[i*n+i]=0;for(auto&v:s)for(auto a:v)for(auto b:v)if(a.first!=b.first)d[a.first*n+b.first]=min(d[a.first*n+b.first],a.second+(long long)b.second);for(int k=0;k<n;k++)for(int i=0;i<n;i++){long long z=d[i*n+k];if(z==INF)continue;auto*row=&d[i*n];auto*mid=&d[k*n];for(int j=0;j<n;j++)if(z+mid[j]<row[j])row[j]=z+mid[j];}while(q--){int x=in.read()-1,y=in.read()-1;long long ans=INF;for(auto a:s[x])for(auto b:s[y])ans=min(ans,a.second+d[a.first*n+b.first]+b.second);printf("%lld\n",ans+w[x]+w[y]);}}

本参考解为独立编写的训练参考解，非官方标准程序。测试数据为自建训练数据。