#3171. 日记和最短路

日记和最短路

该比赛已结束,您无法在比赛模式下递交该题目。您可以点击“在题库中打开”以普通模式查看和递交本题。

题目背景

走路的时候,日记非常喜欢用各种奇怪的方式衡量自己这次走路的效率。

题目描述

日记所在的城市有 nn 个路口和 mm 条连接两个路口的单向道路,且任何两个路口互相(直接或间接)可达。每条道路从第 uiu_i 个路口通向第 viv_i 个路口,且名为 wiw_i。不知道为什么,日记离开一个路口就不能再回去了(也就是说图无环)。

从一个路口到另一个路口可能有很多种路径。一条路径的权值为这条路径经过的每条道路的名字依次相连,例如依次经过道路“awa”“qwq”“ovo”的路径的权值 pp 为“awaqwqovo”。

  1. 有的时候,日记觉得更短的路更优秀,因此她最喜欢走权值 pp 的长度最短的路径。如果有多条路径具有相同的权值长度,她会优先走权值的字典序最小的那条。
  2. 有的时候,日记又会觉得权值更小的路更优秀,因此她会直接优先走权值字典序最小的路径。

对于两个字符串 s,ts, t,我们称 ss 的字典序比 tt 小,当且仅当 i[1,max(s,t)]\exists i \in [1, \max(|s|, |t|)] 满足 s1=t1,s2=t2,,si1=ti1,si<tis_1 = t_1, s_2 = t_2, \dots, s_{i-1} = t_{i-1}, s_i < t_i。对于一个 i>si > |s|,定义 si=0s_i = \texttt{0},其中字符 0\texttt{0} 小于任何其它字符。

日记只会从自己的家所在路口(路口 11)出发,并去向第 nn 个路口。日记想知道,在上述两种情况下,她会优先走的那条路径的权值是什么。你能帮帮她吗?

形式化题意

日记所在城市的路口和道路可以分别抽象为点集 V=[1,n] NV=[1,n] \cap \ N 和边集 E={(u1,v1),(u2,v2),,(um,vm)}E=\{(u_1, v_1), (u_2, v_2), \dots, (u_m, v_m)\},它们组成有向无环图 G(V,E)G(V, E)。每条边 (ui,vi)E(u_i, v_i) \in E 均有一个字符串权 wiw_i

定义一条路径为有序 k(k1)k(k \geq 1) 元组 (a1,a2,,ak)(a_1, a_2, \dots, a_k),满足 1i<k\forall 1 \leq i < k,有 vai=uai+1v_{a_i} = u_{a_{i+1}}。定义一条路径 (a1,a2,,ak)(a_1, a_2, \dots, a_k) 的权值为 wa1,wa2,,wakw_{a_1}, w_{a_2}, \dots, w_{a_k} 顺次连接的结果。

请求出在以下两种情况下点 11 到点 nn 的最小权路径。

  1. 对于两个字符串 s,ts, ts<ts < t 当且仅当 s<t(s=t(i[1,max(s,t)] s.t. s1=t1,s2=t2,,si1=ti1,si<ti))|s| < |t| \vee (|s| = |t| \wedge (\exists i \in [1, \max(|s|, |t|)] \text{ s.t. } s_1 = t_1, s_2 = t_2, \dots, s_{i-1} = t_{i-1}, s_i < t_i))
  2. 对于两个字符串 s,ts, ts<ts < t 当且仅当 i[1,max(s,t)] s.t. s1=t1,s2=t2,,si1=ti1,si<ti\exists i \in [1, \max(|s|, |t|)] \text{ s.t. } s_1 = t_1, s_2 = t_2, \dots, s_{i-1} = t_{i-1}, s_i < t_i

额外定义,对于字符串 ss 和整数 i>si > |s|si=0s_i = \texttt{0},其中 0\texttt{0} 小于任何其它字符。

输入格式

11 行,输入 33 个正整数 n,mn, m

接下来 mm 行,每行输入 22 个正整数 ui,viu_i, v_i11 个只包含小写字母的字符串 wiw_i

输出格式

输出 1122 个字符串,分别代表在情况 1122 时日记会优先走的路径的权值。数据保证,一定存在一条路径使得路口 11 能够到达路口 nn

数据范围

本题设置 25 个测试点,每个测试点 4 分。同时,每个测试点满足一些限制,见下:

测试点编号 n \leq m \leq 特殊性质
11 1010 5050 rr
22
33 100100 10001000
44
55 20002000 40004000 gg
66
77
88 10410^4 rr
99
1010 10410^4
1111 10510^5 2×1052\times 10^5 gg
1212
1313
1414 5×1055\times 10^5 s(1)s(1)
1515
1616
1717
1818 s(2)s(2)
1919
2020
2121
2222 rr
2323
2424 5×1055\times 10^5
2525 5×1055\times 10^5

特别地,特殊性质 g 代表:图为网格图;s(x) 代表:每条边的名(边权) wiw_i 均满足 wi=x|w_i| = xr 代表:数据随机生成。

网格图生成:设网格图尺寸为 x×y(xy=n)x \times y(xy=n),则网格图上每个节点 (i,j)(i, j)(i+1,j)(i + 1, j)(i,j+1)(i, j + 1) 连边(若其存在)。之后,将每个坐标映射为一个路口,保证 (1,1)(1, 1) 处映射为路口 11(x,y)(x, y) 处映射为路口 nn。额外保证 wi=1|w_i| = 1

随机生成:先随机生成一个以 11 为根的叶向树,即 ii 的父亲在 [1,i1][1, i-1] 中等概率随机选取,并从每个节点的父亲向其连边;再随机生成 mn+1m - n + 1 条边:先随机取一个深度不最大的节点 uu,再随机取一个深度严格大于它的点 vv,并连边 (u,v)(u, v)。额外保证 wi4|w_i| \leq 4,并先等概率选取某个长度,再等概率选取该长度的一个合法字符串。

对全部数据,有 1n105,n1m5×105,wi105,wi2×1061 \leq n \leq 10^5, n - 1 \leq m \leq 5 \times 10^5, |w_i| \leq 10^5, \sum |w_i| \leq 2 \times 10^6

输入样例 1

4 6
1 2 aa
1 3 b
1 4 c
2 3 d
2 4 dd
3 4 c

输出样例 1

c aadc

暑假集训第一次提高组模拟

未参加
状态
已结束
规则
IOI
题目
4
开始于
2024-7-16 14:30
结束于
2024-7-18 6:30
持续时间
40 小时
主持人
参赛人数
34