打卡信奥刷题（3131）用C++实现信奥题 P7500 「HMOI R1」地铁客流

P7500 「HMOI R1」地铁客流

题目背景

一座城市的地铁客流量是非常重要的指标，它体现了这座城市正在不断流动着的人口数量。无论通勤还是旅游，都会给这座城市的经济带来活力。

疫情期间各地地铁客流惨淡，甚至有部分城市地铁停运。现在疫情态势好转，各地陆续复工复产，地铁客流量大小也是判断城市复工复产、经济恢复率的重要参考。

题目描述

天穹市的地铁系统由MMM条线路组成，共有NNN座车站，每座车站都会有线路停靠。每条线路的相邻两站之间可视为由无向边连接。其中地铁iii号线上有kik_iki​座车站，这些车站互不相同。

这些线路会在一些车站相交，也就是说，一座车站可能有很多线路停靠。

现在，有PPP位乘客分别想从sjs_jsj​号车站出发，去tjt_jtj​号车站，保证这两座车站不同。当这两座车站不在一条线路上时，他就会进行若干次换乘。作为天穹地铁的技术工作人员，你需要计算这些乘客贡献的客流量。

请注意，在这里使用的客流量计算方法和实际应用中的有所不同。

客流量===进站客流+++换乘客流。进站客流即为乘客数；换乘客流为乘客的换乘次数。起终点之间可能会有多条路径可以选择，此时，地铁客流量与乘客选择的路径无关；计算时，我们只考虑换乘次数最少的路径。

注意：

• 设从sss到ttt最少进行trans\rm transtrans次换乘，则此时要乘坐trans+1\rm trans + 1trans+1条线路，贡献trans+1\rm trans + 1trans+1的客流量。
• 当乘客不能从起点到达终点时，即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

输入 #1

8 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

输出 #1

9

输入输出样例 #2

输入 #2

8 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

输出 #2

7

输入输出样例 #3

输入 #3

8 3 4 4 1 2 3 5 2 3 6 3 7 4 8 1 6 4 3 4 8 6 7

输出 #3

3

说明/提示

样例解释：

• 默认乘客会选择换乘次数最少的路径。
• 边上的数字表示所在地铁线路的编号。

样例 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，只换乘了一次。

总客流量为2+2+1+2=72 + 2 + 1 + 2 = 72+2+1+2=7。

样例 3 如图：

相比样例 1，乘客222和444的出行路径不是通路，不会计入客流量。

总客流量为2+0+1+0=32 + 0 + 1 + 0 = 32+0+1+0=3。

设车站iii停靠的线路数为sizi\mathrm{siz}_isizi​。
对于所有数据：

• 2≤N≤1052 \le N \le 10^52≤N≤105；
• 1≤M≤10001 \le M \le 10001≤M≤1000；
• 1≤P≤1001 \le P \le 1001≤P≤100；
• 1≤sizi≤501 \le \mathrm{siz}_i \le 501≤sizi​≤50。

本题采用捆绑测试。

由于读入量较大，请勿不关流同步使用cin。

你可以通过std::ios::sync_with_stdio(false)来关闭cin的流同步。

你也可以使用以下快速读入模板，支持读入int范围内的非负整数。

intreadInt(){intret=0;charo;while(!isdigit(o=getchar()));doret=ret*10+(o^48);while(isdigit(o=getchar()));returnret;}

• Idea: 南桥汽车站
• Solution: 南桥汽车站
• Code: 南桥汽车站
• Data: 南桥汽车站

C++实现

#include<bits/stdc++.h>usingnamespacestd;constintN=1e5+10,M=1e3+10;intn,m,p;intdist[M][M],sum=0;vector<int>A[N];intmain(){ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);memset(dist,0x3f,sizeofdist);cin>>n>>m>>p;for(inti=1;i<=m;i++){intnum,x;cin>>num;for(intj=1;j<=num;j++){cin>>x;A[x].push_back(i);}}for(inti=1;i<=n;i++){intx=A[i].size();if(x<=1)continue;for(intj=0;j<x;j++)for(intk=j+1;k<x;k++)dist[A[i][j]][A[i][k]]=dist[A[i][k]][A[i][j]]=1;}for(inti=1;i<=m;i++)dist[i][i]=0;for(intk=1;k<=m;k++)for(inti=1;i<=m;i++)for(intj=1;j<=m;j++)dist[i][j]=min(dist[i][j],dist[i][k]+dist[k][j]);for(intk=1;k<=p;k++){inta,b,x,y,ans=0x3f3f3f3f;cin>>a>>b;x=A[a].size(),y=A[b].size();for(inti=0;i<x;i++)for(intj=0;j<y;j++)ans=min(dist[A[a][i]][A[b][j]]+1,ans);if(ans!=0x3f3f3f3f)sum+=ans;}cout<<sum;return0;}

后续

接下来我会不断用C++来实现信奥比赛中的算法题、GESP考级编程题实现、白名单赛事考题实现，记录日常的编程生活、比赛心得，感兴趣的请关注，我后续将继续分享相关内容