P7500 「HMOI R1」地铁客流题目背景一座城市的地铁客流量是非常重要的指标它体现了这座城市正在不断流动着的人口数量。无论通勤还是旅游都会给这座城市的经济带来活力。疫情期间各地地铁客流惨淡甚至有部分城市地铁停运。现在疫情态势好转各地陆续复工复产地铁客流量大小也是判断城市复工复产、经济恢复率的重要参考。题目描述天穹市的地铁系统由MMM条线路组成共有NNN座车站每座车站都会有线路停靠。每条线路的相邻两站之间可视为由无向边连接。其中地铁iii号线上有kik_iki​座车站这些车站互不相同。这些线路会在一些车站相交也就是说一座车站可能有很多线路停靠。现在有PPP位乘客分别想从sjs_jsj​号车站出发去tjt_jtj​号车站保证这两座车站不同。当这两座车站不在一条线路上时他就会进行若干次换乘。作为天穹地铁的技术工作人员你需要计算这些乘客贡献的客流量。请注意在这里使用的客流量计算方法和实际应用中的有所不同。客流量进站客流换乘客流。进站客流即为乘客数换乘客流为乘客的换乘次数。起终点之间可能会有多条路径可以选择此时地铁客流量与乘客选择的路径无关计算时我们只考虑换乘次数最少的路径。注意设从sss到ttt最少进行trans\rm transtrans次换乘则此时要乘坐trans1\rm trans 1trans1条线路贡献trans1\rm trans 1trans1的客流量。当乘客不能从起点到达终点时即s,ts, ts,t之间没有通路他就会去坐公交此时客流量计为000。输入格式第一行三个整数N,M,PN, M, PN,M,P。接下来MMM行每行表示一条地铁线路每行第一个整数为ki (2≤ki≤N)k_i\ (2 \le k_i \le N)ki​(2≤ki​≤N)为这条线的车站数后面kik_iki​个整数q (1≤q≤N)q\ (1 \le q \le N)q(1≤q≤N)为这条线路依次经过的车站编号。接下来PPP行每行两个整数sj,tj (1≤sj,tj≤N; sj≠tj)s_j, t_j\ (1 \le s_j, t_j \le N;\ s_j \neq t_j)sj​,tj​(1≤sj​,tj​≤N;sj​tj​)表示一位乘客的出行起终点。输出格式仅一行一个整数表示这些乘客贡献的客流量。输入输出样例 #1输入 #18 4 4 4 1 2 3 5 2 3 6 2 2 4 3 7 4 8 1 6 4 3 4 8 6 7输出 #19输入输出样例 #2输入 #28 4 4 4 1 2 3 5 3 6 3 8 2 2 4 3 7 4 8 1 6 4 3 4 8 6 7输出 #27输入输出样例 #3输入 #38 3 4 4 1 2 3 5 2 3 6 3 7 4 8 1 6 4 3 4 8 6 7输出 #33说明/提示样例解释默认乘客会选择换乘次数最少的路径。边上的数字表示所在地铁线路的编号。样例 1 如图乘客111会乘坐111号线从111到333再乘坐222号线从333到666乘客222会乘坐333号线从444到222再乘坐111号线从222到333乘客333会乘坐444号线从444到888乘客444会乘坐222号线从666到333乘坐111号线从333到222再乘坐333号线从222到444最后乘坐444号线从444到777。如上四个人分别贡献了2,2,1,42, 2, 1, 42,2,1,4的客流量答案为999。样例 2 如图相比样例 1乘客222可以选择另外一条路线即乘坐444号线从444到888再乘坐222号线从888到333也是换乘一次的乘客444可以选择另外一条换乘次数更少的的路线乘坐444号线从777到888再乘坐222号线从888到666只换乘了一次。总客流量为221272 2 1 2 722127。样例 3 如图相比样例 1乘客222和444的出行路径不是通路不会计入客流量。总客流量为201032 0 1 0 320103。设车站iii停靠的线路数为sizi\mathrm{siz}_isizi​。对于所有数据2≤N≤1052 \le N \le 10^52≤N≤1051≤M≤10001 \le M \le 10001≤M≤10001≤P≤1001 \le P \le 1001≤P≤1001≤sizi≤501 \le \mathrm{siz}_i \le 501≤sizi​≤50。本题采用捆绑测试。No.ConstraintsScore111N,P≤5; M≤3N, P \le 5;\ M \le 3N,P≤5;M≤3101010222ki2k_i 2ki​2202020333N,M≤50; P≤10N, M \le 50;\ P \le 10N,M≤50;P≤10202020444M≤500; P≤10M \le 500;\ P \le 10M≤500;P≤10202020555No further constraints303030由于读入量较大请勿不关流同步使用cin。你可以通过std::ios::sync_with_stdio(false)来关闭cin的流同步。你也可以使用以下快速读入模板支持读入int范围内的非负整数。intreadInt(){intret0;charo;while(!isdigit(ogetchar()));doretret*10(o^48);while(isdigit(ogetchar()));returnret;}Idea: 南桥汽车站Solution: 南桥汽车站Code: 南桥汽车站Data: 南桥汽车站C实现#includebits/stdc.husingnamespacestd;constintN1e510,M1e310;intn,m,p;intdist[M][M],sum0;vectorintA[N];intmain(){ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);memset(dist,0x3f,sizeofdist);cinnmp;for(inti1;im;i){intnum,x;cinnum;for(intj1;jnum;j){cinx;A[x].push_back(i);}}for(inti1;in;i){intxA[i].size();if(x1)continue;for(intj0;jx;j)for(intkj1;kx;k)dist[A[i][j]][A[i][k]]dist[A[i][k]][A[i][j]]1;}for(inti1;im;i)dist[i][i]0;for(intk1;km;k)for(inti1;im;i)for(intj1;jm;j)dist[i][j]min(dist[i][j],dist[i][k]dist[k][j]);for(intk1;kp;k){inta,b,x,y,ans0x3f3f3f3f;cinab;xA[a].size(),yA[b].size();for(inti0;ix;i)for(intj0;jy;j)ansmin(dist[A[a][i]][A[b][j]]1,ans);if(ans!0x3f3f3f3f)sumans;}coutsum;return0;}后续接下来我会不断用C来实现信奥比赛中的算法题、GESP考级编程题实现、白名单赛事考题实现记录日常的编程生活、比赛心得感兴趣的请关注我后续将继续分享相关内容