写在前面的话
本场比赛难度估计大约可能是 \(\text{NOIp}\) 难度？
考场得分 \(100+100+100+0=300\) ,封榜时排名 \(\text{rank6}\) 。
T1
题目描述：
有一张地铁交通网 \(G\)．\(G\) 拥有 \(n\) 个站点和 \(m\) 条地铁线路．
第 \(i\) 条地铁线路 \(P_i\) 会经过交通网上的若干站点，形如 \(P_i=(u_1,u_2,u_3,...,u_{k_i})(k_i>0)\)：每两个相邻站点 \(u_j,u_{j+1}(j<k_i)\) 之间存在一段属于线路 \(i\) 的从 \(u_j\) 通向 \(u_{j+1}\) 的单向地铁轨道．保证一条地铁线路不重复经过同一站点．但一个站点可能被若干条地铁线路经过>
一种出行方案具体是这样的：从 \(1\) 号站点出发，选定一条经过 \(1\) 号站点的地铁线路并开始乘坐地铁．沿当前地铁线路乘坐地铁的过程中，可以选择换乘其他任意一条经过当前站点的地铁线路．要求最终到达 \(n\) 号站点．乘坐地铁过程中重复经过某一站点或某段地铁轨道是被允许的．并且我们认为从一号节点出发不算换乘。
现在有 \(q\) 个询问，每一次询问给出 \(a,b,c\) 。如果你的路途经过了 \(x\) 条地铁轨道并且换乘了 \(b\) 次，疲劳值就是 \(ax+by\) 。问在换乘不超过 \(c\) 次的最小疲劳值。
\(1\le n \le 10^5\)，\(1\le m \le 10^4\)，\(1\le q \le 10^5\)，\(\sum k_i \le 3\times 10^5\)．
\(0 \leqslant c \leqslant 20\) 。
思路点拨：
题目描述略难懂。我也不好表述所以使用了原题体面并略加修改。
我们发现 \(ax+by(y \leqslant c)\) 的式子十分的抽象，但是我们看见 \(c\) 其实非常的小，我们不妨枚举式子中的 \(y\) 是多少，那么我们唯一需要考虑的是在固定一个 \(y\) 的情况下，\(x\) 最小可以是多少。所以我们果断设计一个状态 \(dp_{i,j}\) 表示目前在节点 \(i\) ,换乘次数为 \(j\) 的最短路径长度。其中 \(dp_{1,0}=0\) 。
但是我们如果直接在图上转移会有大问题，因为同一个节点不一定只被一条地铁经过，我们就无法处理换乘的信息了。我们考虑一个图论建模，我们对于每一个节点都建立一个中转节点，每一条地铁线路（我们直接新建一些节点来代表线路）向中转节点连一条有向边 ；地铁中转节点又向每一个经过这个节点的点连有向边。
之后我们的转移这么考虑。现在有一个状态 \(dp_{u,j}\) ，如果存在一条有向边 \((u,v)\) ，那么 \(v\) 我们分三类讨论：
-
这条边十分平凡：\(dp_{v,j}=dp_{u,j}+1\)
-
这条边的 \(v\) 是中转节点： \(dp_{v,j+1}=dp_{u,j}\)
-
这条边的 \(u\) 是中转节点： \(dp_{v,j}=dp_{u,j}\)
我们可以通过上述方式转移，但是我们并不知道转移顺序。注意到转移的时候，每一条边的边权是 \(0,1\) 。我们可以使用 \(\text{01-bfs}\) 进行转移。特别值得注意的是，为了方便，我们应该要将终点设为 \(n\) 的中转节点，不然就要枚举每一个复制出来的 \(n\) 节点十分麻烦。可是每一次进入中转节点都会导致换乘次数加一，所以我们可以将 \(dp_{i,j}\) 的 \(j\) 这一维度开到 \(c+1\) ，统计答案的时候少算一次换乘就可以。
答案的统计十分简单，我们暴力枚举换乘次（贡献就 \(by\)）数用 \(dp\) 数组帮我们回答 \(ax\) 这一部分的最小值。