DS图—图的最短路径（无框架）迪杰斯特拉算法

题目描述

给出一个图的邻接矩阵，输入顶点v，用迪杰斯特拉算法求顶点v到其它顶点的最短路径。

输入

第一行输入t，表示有t个测试实例

第二行输入顶点数n和n个顶点信息

第三行起，每行输入邻接矩阵的一行，以此类推输入n行

第i个结点与其它结点如果相连则为距离，无连接则为0，数据之间用空格隔开。

第四行输入一个顶点v，表示求该顶点v到其他顶点的最短路径距离

以此类推输入下一个示例

输出

对每组测试数据，输出：

每行输出顶点v到某个顶点的最短距离和最短路径

每行格式：顶点v编号-其他顶点编号-最短路径值----[最短路径]。没有路径输出：顶点v编号-其他顶点编号--1。具体请参考示范数据

输入样例1 

2 5 0 1 2 3 4 0 5 0 7 15 0 0 5 0 0 0 0 0 0 1 0 0 2 0 0 0 0 0 0 0 0 6 V0 V1 V2 V3 V4 V5 0 0 10 0 30 100 0 0 5 0 0 0 0 0 0 50 0 0 0 0 0 0 0 10 0 0 0 20 0 60 0 0 0 0 0 0 V0

输出样例1

0-1-5----[0 1 ] 0-2-9----[0 3 2 ] 0-3-7----[0 3 ] 0-4-10----[0 3 2 4 ] V0-V1--1 V0-V2-10----[V0 V2 ] V0-V3-50----[V0 V4 V3 ] V0-V4-30----[V0 V4 ] V0-V5-60----[V0 V4 V3 V5 ]

输入样例2

14 24 Hv FM ys uA uf wK sJ Ll Xz Rc dj UP IP sr Nf Jx Mn eA WL ek bb Yq dz oR 0 0 0 0 0 0 0 0 0 0 0 63 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 39 0 0 0 0 0 0 0 0 0 91 0 0 0 0 0 0 0 0 0 0 0 0 61 80 48 0 0 0 0 0 32 0 0 0 0 0 0 0 0 0 15 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 80 0 0 0 62 79 0 40 0 0 0 0 70 0 0 0 0 0 0 0 32 0 0 0 0 0 0 0 0 0 0 0 0 84 0 0 0 0 0 0 98 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 30 0 0 0 36 0 0 0 81 0 0 0 0 0 0 0 0 0 0 0 0 0 32 0 0 0 94 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 41 0 0 0 0 35 0 0 75 0 0 0 0 0 0 91 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 48 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 87 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 100 0 0 0 0 0 0 0 0 0 0 0 0 0 75 19 0 0 0 0 70 0 0 0 0 59 0 12 0 0 0 0 0 0 19 0 0 0 0 0 0 0 0 0 90 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 41 0 0 0 0 0 0 0 71 0 0 0 0 0 68 0 0 0 0 0 0 0 0 0 0 0 0 0 0 72 0 0 0 0 0 0 0 0 0 0 0 0 0 63 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 85 0 55 23 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 23 0 0 0 0 0 0 0 0 0 0 68 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 83 0 0 19 0 90 0 0 0 0 0 0 0 0 0 0 0 0 0 0 17 0 71 0 0 0 0 0 0 0 0 0 0 0 0 0 10 0 0 40 0 0 0 0 0 0 0 0 0 64 58 0 0 0 0 0 0 0 0 0 0 0 0 ys 24 NO Kh LZ mu Uw FX Jj Jn NX FD uC fO Kp gY lm yk sS bu HI tB MG yP kv is 0 0 0 0 0 0 16 0 0 65 65 68 28 0 0 0 0 0 0 50 0 0 0 0 0 0 95 0 44 0 0 0 99 0 0 0 0 0 0 0 45 38 21 85 0 85 0 0 0 0 0 43 45 0 38 0 59 0 61 28 10 0 0 0 61 0 0 0 36 0 86 51 85 0 0 0 93 0 0 16 0 23 33 0 95 0 0 59 0 58 70 0 64 0 0 20 0 0 0 10 0 12 0 50 75 0 0 0 0 20 82 94 61 24 0 0 47 0 13 64 0 0 24 99 0 0 18 56 0 0 0 0 0 0 0 10 0 0 0 11 0 0 0 0 0 0 52 0 0 30 0 0 0 0 0 0 0 51 0 16 0 0 0 0 0 0 0 24 48 0 0 0 0 90 0 0 96 0 0 0 91 0 18 0 90 0 0 0 46 16 0 0 0 85 0 0 0 0 12 91 0 0 0 0 90 0 0 0 0 0 42 0 0 0 0 0 0 0 11 0 0 0 27 86 14 0 0 0 94 0 0 21 84 0 90 24 0 74 0 0 66 0 0 0 0 0 51 0 0 0 0 0 0 16 0 0 0 0 41 0 0 0 0 0 0 96 0 61 25 95 0 94 57 0 0 0 0 0 0 0 0 0 0 98 41 0 0 34 87 86 0 0 0 10 43 0 0 0 0 39 0 0 0 0 29 10 34 0 0 58 0 64 0 69 0 0 0 0 0 15 0 52 0 58 0 0 12 0 0 60 0 0 0 37 65 0 75 92 57 0 68 22 0 0 0 96 31 0 0 0 0 0 0 51 0 34 0 0 0 0 20 0 0 0 66 78 0 62 58 0 0 0 0 0 0 0 0 0 42 0 0 0 0 53 0 0 51 0 0 0 0 0 0 45 0 57 0 46 0 0 0 39 0 97 87 0 27 0 0 0 0 0 93 0 0 23 11 0 29 36 37 69 0 0 0 0 0 84 32 0 0 0 0 38 0 0 0 0 0 47 52 0 0 21 0 0 0 0 66 0 0 62 0 0 17 0 60 0 98 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 31 0 0 41 55 57 26 12 0 63 0 0 0 26 77 0 0 34 0 0 27 0 0 80 67 34 0 0 0 0 0 37 0 0 0 0 26 90 0 51 79 0 37 0 0 0 0 0 10 0 0 0 0 44 0 0 0 87 0 31 76 45 68 0 0 73 0 0 58 0 0 0 0 0 0 0 0 0 0 15 93 94 0 0 30 0 0 41 0 0 95 0 0 100 0 0 0 0 0 0 0 0 HI 22 xS FA jT uu BH Ze yA Zg zG Bw nO iJ bA ff BN cG lV ZL ah mP TS Jh 0 0 30 0 0 0 27 0 69 0 0 35 0 0 0 0 0 0 0 0 0 0 0 0 75 0 0 32 0 0 0 0 88 0 49 52 0 0 0 0 0 0 0 54 0 0 0 0 0 0 0 0 0 0 25 0 0 0 0 0 0 0 19 88 0 0 0 0 0 0 0 0 0 0 0 0 0 83 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 74 0 0 0 0 0 0 0 89 17 0 0 0 0 0 0 0 0 18 0 0 0 0 0 0 0 0 0 73 0 0 0 98 0 0 0 0 0 48 45 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 21 0 0 0 54 0 76 0 95 70 0 64 0 0 0 0 0 46 57 0 0 0 0 0 0 0 0 0 0 0 98 0 17 0 0 0 0 62 0 0 0 0 0 0 0 0 0 0 0 0 0 54 0 0 0 0 0 0 0 0 0 0 64 0 0 0 0 41 0 0 0 86 0 0 0 0 0 0 0 54 0 0 0 54 0 62 0 23 0 0 0 0 0 17 0 0 0 0 0 0 0 0 0 0 0 32 77 0 0 0 29 35 0 31 0 0 98 0 0 0 0 35 0 27 39 92 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 90 0 0 50 0 0 31 0 80 0 0 0 0 0 0 0 0 0 67 0 0 0 0 0 0 0 0 0 0 0 0 0 0 32 0 0 0 24 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 15 0 29 45 0 0 0 63 0 0 0 0 36 0 0 0 0 99 0 0 0 0 0 0 0 0 0 0 0 0 56 0 0 47 0 0 33 0 0 47 0 0 0 0 0 0 0 0 0 0 0 0 0 16 20 0 0 0 0 0 0 0 15 0 0 14 0 0 0 0 0 0 61 0 0 19 0 71 0 0 0 0 0 0 0 44 0 78 0 0 0 0 0 0 0 94 0 23 0 70 0 0 0 0 49 0 44 0 0 88 0 0 0 0 49 24 0 0 100 0 0 0 0 0 0 yA 25 Cq em Ay uA eH Tq yd nY Nz nm kl yu SH eR UH YP FB gs MB dO Sb uv aO uf gu 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 35 0 30 0 47 0 71 0 0 0 0 0 0 0 0 0 60 0 67 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 33 57 0 0 0 0 0 0 0 0 79 0 0 0 0 0 77 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 32 59 0 31 0 0 23 44 0 33 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 40 0 0 0 0 0 0 0 0 41 0 0 0 0 0 20 0 34 34 51 0 0 0 0 0 0 0 0 0 0 0 0 88 0 0 0 0 0 0 0 69 0 0 0 0 0 0 0 69 0 0 0 0 62 21 0 0 0 0 0 0 0 0 98 0 86 0 0 0 0 0 81 32 0 0 0 0 0 0 79 0 0 0 0 0 0 95 0 0 29 0 15 0 0 0 0 0 0 0 67 0 26 65 0 0 0 0 0 0 0 0 61 0 0 0 0 0 0 0 36 0 0 0 0 42 0 0 0 85 0 0 0 0 0 14 0 68 16 0 0 0 0 0 0 0 0 0 0 0 0 0 43 0 0 0 0 0 0 0 0 0 0 0 0 61 0 0 0 0 44 17 0 13 35 15 0 0 91 0 0 0 0 10 79 0 96 0 0 0 0 84 0 0 0 0 0 0 0 0 50 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 24 0 59 0 68 0 38 0 0 0 0 0 0 0 12 0 0 68 0 0 0 0 0 0 0 0 58 0 0 0 33 0 0 24 0 0 0 53 0 40 0 0 0 0 0 0 0 0 0 89 0 0 89 0 35 0 0 83 0 0 0 0 0 0 0 37 0 0 0 0 82 0 0 0 0 0 0 0 0 0 0 0 0 20 0 0 0 0 0 0 0 0 21 0 96 0 0 0 0 0 0 0 36 0 0 0 39 0 0 32 0 0 0 0 0 72 0 0 0 0 0 0 11 0 0 0 0 32 0 48 0 0 0 0 0 0 99 0 0 0 0 96 59 0 0 45 0 49 94 0 11 0 72 0 0 0 71 0 0 0 0 0 0 0 0 0 0 0 0 82 0 0 0 0 0 0 38 0 0 0 0 0 21 0 0 0 0 0 0 0 0 0 75 0 11 0 0 0 0 35 0 0 0 99 67 80 0 0 35 91 0 0 0 0 0 13 0 0 0 0 0 0 44 0 0 0 0 0 0 0 26 0 0 0 0 48 22 0 61 0 67 0 0 0 72 0 0 53 0 0 0 0 0 74 0 0 0 0 0 81 0 0 0 0 0 0 0 0 0 34 0 64 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 SH 20 kd di Da Cz Yz Rw Zs jt of nf QP wq tZ AY MW Py ZK TD uJ Ew 0 0 0 61 0 0 65 0 37 0 40 0 0 0 0 45 66 0 41 0 0 0 46 81 0 100 80 0 0 0 0 46 30 0 59 0 0 0 12 0 65 89 0 0 100 0 0 56 0 75 0 94 27 0 34 0 49 18 94 36 0 0 0 0 0 0 0 32 77 0 58 0 0 0 0 0 0 69 0 44 0 18 0 43 0 31 77 14 54 0 0 95 0 0 88 0 0 0 17 81 0 95 44 50 71 0 0 0 36 0 16 41 0 0 37 0 94 0 47 0 0 26 0 0 0 31 0 81 0 30 91 0 42 0 0 80 0 0 0 15 0 43 0 0 14 0 0 0 32 58 95 0 79 0 16 0 57 0 32 87 0 0 55 34 22 79 37 67 0 0 0 67 74 0 77 0 0 0 0 0 27 76 79 0 0 0 99 74 69 0 0 27 82 0 0 0 49 12 66 60 45 51 0 11 27 0 0 21 0 35 0 0 0 90 0 0 74 0 61 45 0 0 52 41 83 0 0 30 0 0 0 0 13 90 51 0 0 99 0 72 69 94 71 0 29 12 67 0 0 34 0 29 0 0 89 47 56 81 0 0 59 0 0 0 29 0 0 0 0 20 42 0 64 0 45 0 0 0 17 0 0 35 0 0 58 0 0 0 0 0 24 0 76 69 0 44 53 61 0 0 60 0 0 75 39 0 11 49 14 0 60 0 0 0 17 0 11 0 0 55 0 0 11 0 0 0 79 0 0 0 20 0 0 0 49 64 0 0 91 53 0 0 58 26 0 0 11 0 0 0 87 0 37 0 26 18 19 0 36 0 0 78 0 27 72 23 16 0 0 0 30 0 0 0 0 70 95 62 0 36 0 0 0 53 93 85 0 0 67 0 97 0 29 0 0 59 26 0 83 0 Yz 22 wm bQ Er OY od xz jN PS eV LF Yr Dk cN cq WV Ew dn uF yd oI Wg Bc 0 0 0 0 0 0 58 0 0 64 0 0 0 87 0 0 0 0 0 44 0 0 24 0 0 0 0 0 0 22 0 0 0 92 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 14 61 0 0 0 0 0 88 0 0 0 0 0 0 0 0 0 0 23 0 0 0 0 0 0 0 0 0 0 22 0 0 0 0 39 0 0 0 0 0 0 0 0 86 0 0 91 0 0 0 0 99 0 0 0 0 40 0 0 0 0 0 0 0 0 0 32 0 0 0 0 0 0 91 0 0 0 0 0 50 0 82 0 0 0 0 0 0 0 77 0 0 20 0 0 0 0 0 0 73 54 0 0 0 0 0 0 75 0 75 0 0 0 0 30 0 0 34 0 0 0 0 0 0 0 0 0 71 0 0 0 0 99 0 0 67 0 0 0 0 0 0 46 0 0 0 0 0 0 0 0 0 0 0 0 54 0 48 0 0 26 0 0 14 0 0 0 0 0 0 0 0 0 0 34 0 0 78 0 0 65 0 68 0 69 0 0 0 53 0 0 0 0 0 0 17 0 0 0 0 0 0 0 72 0 0 0 0 0 0 0 0 33 0 0 93 98 0 78 0 0 0 0 0 0 0 0 59 99 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 34 0 0 0 0 0 0 0 0 0 81 0 0 0 26 0 55 0 0 0 0 0 0 0 0 0 67 0 0 0 0 0 0 97 0 0 0 0 0 0 66 0 26 0 0 89 0 0 0 0 0 48 0 81 0 0 0 0 0 0 0 34 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 59 0 0 0 0 66 0 0 0 0 0 0 0 0 0 16 0 0 0 73 0 0 0 0 0 0 0 0 28 0 0 0 0 0 40 0 0 0 0 0 0 0 0 55 0 0 0 74 0 0 0 0 0 0 0 0 0 0 0 0 75 0 0 18 90 0 0 0 0 35 0 0 0 0 0 0 0 0 0 0 0 61 0 0 50 0 0 0 0 57 0 0 98 100 0 0 0 0 0 0 0 0 0 0 0 0 Wg 22 qL kN fx wz Qe bS MP xB Ox AA LY xY ds fC Ge Qg xr kR EM QF oY QQ 0 0 0 0 96 0 0 0 0 0 0 0 16 0 0 18 64 0 0 75 0 0 0 0 44 0 0 0 17 0 0 0 11 0 0 0 84 0 0 0 0 0 0 0 0 95 0 53 100 94 0 31 0 0 66 0 49 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 55 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 72 0 0 0 0 0 19 51 0 0 0 0 0 34 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 92 0 0 15 0 85 0 0 0 39 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 27 0 0 0 84 0 0 20 40 0 0 49 0 0 0 0 0 0 0 0 0 0 14 0 41 25 0 0 0 0 0 0 26 0 19 0 0 0 0 0 35 58 0 0 0 0 0 0 0 0 56 0 0 0 0 0 0 0 0 0 0 0 0 0 95 0 0 0 26 0 88 0 0 0 0 0 0 0 0 0 0 0 97 0 40 0 0 0 0 0 0 0 26 0 0 0 0 0 0 0 0 0 0 0 0 0 24 0 0 0 0 0 12 0 0 0 0 0 93 0 0 15 0 0 0 0 0 0 0 0 0 0 0 0 99 0 0 0 0 0 0 25 0 0 0 0 0 38 0 0 0 0 45 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 12 0 0 0 0 0 0 0 0 0 0 0 0 95 0 0 0 0 0 88 0 0 0 0 82 0 0 0 0 93 0 0 0 0 0 0 0 0 0 0 0 44 0 0 0 0 0 0 0 0 88 0 31 87 0 0 0 0 0 0 0 0 0 0 55 0 56 81 0 0 0 0 0 0 0 0 0 90 0 0 0 0 0 58 0 0 0 0 0 0 0 0 0 0 0 66 0 0 0 0 0 0 0 0 49 0 0 93 0 0 0 18 76 0 0 0 0 0 0 0 0 30 0 0 70 0 0 0 0 0 58 0 0 0 0 0 0 0 0 0 0 0 0 0 AA 24 iW OV xm ma pB sA EK qD Aw cn my Kg nP zN zK Nn gu JH sX KJ Od Mm iM wQ 0 100 0 0 0 0 0 0 52 0 0 0 49 0 0 0 0 0 0 0 0 10 0 0 0 0 0 0 0 0 0 22 0 0 0 82 0 0 0 0 0 0 94 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 88 0 0 47 60 0 0 0 75 0 0 0 64 0 0 0 65 0 0 0 0 0 82 0 0 0 0 0 0 0 0 97 0 0 0 0 0 34 0 0 0 0 0 0 27 0 0 0 0 82 13 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 41 0 0 0 0 0 0 0 0 0 0 0 0 0 0 32 0 0 0 0 83 0 0 0 0 0 0 0 0 25 0 0 0 0 0 0 0 0 0 0 0 0 0 47 0 0 0 0 0 52 0 0 0 0 21 0 0 0 0 0 0 0 0 61 0 0 0 0 0 0 48 0 79 26 0 0 46 0 0 0 0 25 58 0 0 0 0 0 13 0 0 0 0 47 48 0 0 0 83 82 0 0 0 0 0 10 0 16 0 32 38 0 0 0 0 0 89 0 0 0 0 57 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 21 0 0 81 54 0 0 0 0 0 0 29 66 0 0 0 0 14 66 0 0 0 0 0 0 100 0 0 0 0 0 0 0 0 0 0 0 21 0 0 74 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 70 0 66 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 13 0 0 0 0 0 0 0 0 0 0 0 23 0 0 0 0 0 100 0 0 76 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 68 0 35 0 0 0 0 0 0 0 24 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 37 75 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 91 0 0 0 0 0 87 0 0 0 0 0 0 64 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 61 0 0 21 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 52 38 0 0 0 0 0 85 0 0 0 0 0 0 0 0 0 0 0 0 0 0 81 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 72 0 0 0 0 0 0 0 0 0 0 0 0 28 71 0 17 0 0 0 0 0 0 0 0 0 0 KJ 24 kp QJ jw Si MU cg td Bq qQ of hW XY kA ld EY jL zf OS Ua nS yj Dt ln lw 0 0 0 0 0 0 0 0 88 0 86 0 84 0 0 0 0 0 59 0 0 59 0 0 0 0 0 0 0 13 0 90 0 0 0 0 0 40 60 0 0 0 0 0 0 0 86 0 63 0 0 0 85 0 0 0 0 0 0 0 0 0 20 0 80 0 0 0 0 44 0 96 0 93 0 0 0 0 0 87 0 0 0 0 0 0 0 0 0 62 0 0 0 24 0 0 0 0 0 0 0 0 0 0 0 0 76 35 0 53 0 0 0 0 0 0 91 0 0 0 50 0 0 15 48 0 41 0 0 0 0 0 0 46 0 0 0 0 25 22 0 0 0 0 0 0 0 0 0 0 0 0 62 0 0 0 0 0 0 83 0 65 0 0 16 0 0 0 0 0 0 15 0 28 0 0 0 0 0 0 73 61 0 0 0 0 0 39 10 0 0 0 0 0 84 0 0 0 0 28 0 0 0 0 0 0 0 0 0 0 94 0 0 0 0 0 0 0 0 0 32 11 0 0 0 0 0 0 0 0 87 0 0 0 85 49 0 0 0 0 0 0 0 20 0 29 96 0 0 43 0 0 99 0 0 0 0 0 0 0 0 64 12 0 0 10 0 0 99 0 0 92 0 0 0 0 0 0 0 0 0 0 0 0 86 0 26 0 0 0 0 0 45 0 0 0 0 0 0 76 0 0 0 67 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 96 0 48 0 0 0 0 0 0 0 0 48 0 0 57 0 0 0 0 38 0 15 98 86 11 79 83 0 0 0 0 0 62 0 0 0 0 0 21 0 0 0 0 90 0 0 0 0 0 0 0 0 0 21 0 75 0 78 0 0 79 0 0 0 0 54 0 0 0 0 73 0 0 0 89 0 0 0 0 83 0 0 48 0 0 0 0 99 0 0 94 0 0 0 0 0 0 0 0 59 11 91 0 0 0 80 0 0 0 0 0 82 80 0 0 16 0 88 0 57 0 0 0 25 78 0 0 0 0 0 0 0 41 0 50 89 0 0 56 0 0 0 0 0 43 0 0 0 0 0 0 0 0 37 0 0 0 0 0 0 0 0 87 0 0 0 0 0 0 0 0 0 0 0 12 0 79 0 0 0 0 0 0 26 0 0 0 86 84 0 0 0 0 0 0 94 0 0 0 0 0 54 58 0 0 24 0 18 0 0 0 0 0 91 0 0 0 32 20 35 86 35 0 0 0 27 0 0 0 0 0 0 0 56 0 0 0 0 0 0 0 0 90 0 0 0 0 67 0 0 40 25 0 0 0 0 0 Dt 23 xh xO TO Tc ZR iN ei Jo Gj ut Ed bu kI BP Lj DK VN rj TH WU Bw XL oC 0 28 0 0 0 0 97 0 47 95 64 0 10 0 0 82 0 0 0 0 0 0 15 0 0 0 0 98 49 0 64 25 41 0 0 0 0 71 87 54 0 0 59 26 0 0 20 0 0 0 0 0 0 0 0 0 0 0 0 47 58 36 0 0 0 83 13 0 0 0 0 73 0 44 85 0 0 0 0 0 0 54 0 0 19 26 0 72 96 0 0 0 38 0 0 0 0 24 0 0 0 67 33 0 0 0 0 0 90 14 0 81 86 62 0 0 0 22 87 36 0 0 69 0 0 0 0 0 0 0 86 85 0 57 0 12 0 62 26 96 0 67 71 0 0 43 0 0 0 60 97 72 0 0 67 0 77 79 0 0 0 50 11 91 0 0 0 0 0 0 63 24 0 0 0 0 0 28 0 35 70 0 0 25 0 0 0 0 0 0 0 0 0 0 50 0 0 0 0 0 0 0 82 0 0 82 0 0 0 0 58 0 0 0 39 67 0 0 28 33 13 0 12 54 0 47 0 95 69 0 72 0 69 0 0 0 53 0 68 0 0 99 0 53 0 10 53 0 0 20 0 0 0 0 0 28 96 38 67 0 53 0 93 87 0 62 0 0 0 0 0 38 53 42 49 77 35 0 0 0 32 0 0 0 99 42 0 52 0 78 98 0 58 0 14 0 18 0 17 58 0 0 0 55 0 0 94 17 69 60 24 99 0 0 0 98 58 48 38 31 72 71 30 0 52 0 0 0 25 0 0 99 63 0 50 20 0 99 50 49 68 0 0 0 0 46 0 0 25 0 0 68 46 0 65 0 27 95 88 0 0 41 67 99 0 0 0 21 27 20 37 43 0 15 0 0 0 0 0 33 0 0 0 27 0 78 22 65 0 59 0 12 77 31 0 80 0 0 0 0 0 0 70 77 79 0 57 0 0 0 0 0 82 0 0 93 0 0 0 0 0 82 14 29 0 57 0 46 0 0 0 67 0 0 0 0 0 0 0 0 37 53 54 0 0 0 0 22 46 39 82 80 0 0 0 0 0 26 0 84 43 51 13 0 92 81 0 74 16 0 100 47 50 0 20 0 0 34 0 0 0 100 0 0 0 0 0 22 0 0 0 0 0 57 94 52 42 92 27 19 27 0 71 0 0 32 72 34 98 0 0 85 11 70 0 0 0 86 30 0 0 0 0 0 0 0 0 0 0 Lj 24 dj BK Ce jl re OT uL aF iU aw XG kc VM eq RV Pw fj lD Xk JN km Hq XT ZN 0 0 0 0 0 0 0 43 0 0 0 0 29 0 0 0 0 23 0 0 0 0 0 0 0 0 0 0 0 0 0 60 0 0 0 0 50 0 0 0 82 0 0 0 0 0 0 0 0 0 0 57 0 0 0 0 0 0 0 52 0 0 0 0 0 0 0 0 0 48 29 0 0 0 0 0 0 0 0 0 0 0 0 20 0 0 87 0 25 0 0 0 0 0 0 52 0 0 0 0 0 23 0 0 0 0 0 0 92 0 0 33 0 0 21 0 0 0 0 0 0 0 0 12 0 0 0 0 0 0 0 67 0 0 0 0 48 0 0 0 0 0 0 0 0 0 0 0 46 0 0 0 0 0 0 0 0 0 0 0 0 0 72 0 0 0 0 0 11 0 0 0 74 0 78 0 0 0 45 0 0 0 48 0 0 0 94 0 0 0 44 0 0 0 0 0 0 0 0 0 0 42 0 0 0 0 0 88 0 0 71 0 0 0 0 0 0 0 71 0 0 84 0 0 0 0 0 0 0 97 0 0 0 0 0 0 66 0 0 0 0 0 0 0 0 0 99 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 11 0 0 87 0 0 0 0 69 10 70 0 0 0 0 36 0 0 0 0 0 0 0 17 92 0 0 0 0 0 0 49 26 0 0 53 0 0 0 0 0 0 0 0 0 0 0 0 0 0 71 0 0 70 71 0 0 0 0 37 34 0 0 0 0 82 0 0 0 0 54 0 0 0 0 97 0 0 0 0 0 0 0 0 0 0 0 0 0 13 0 56 0 79 0 0 0 64 0 0 54 94 0 0 49 0 80 0 0 0 49 0 0 0 0 49 0 0 0 50 0 0 41 0 0 0 90 0 0 0 0 0 0 0 0 0 0 56 0 0 0 0 0 0 0 0 0 52 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 97 0 0 0 26 32 0 0 0 0 0 100 0 0 0 0 0 0 0 0 0 18 0 73 0 0 0 0 17 0 0 0 0 0 0 0 0 0 0 0 0 0 96 0 0 0 0 50 63 0 0 0 0 0 19 0 0 81 0 0 0 0 0 0 86 0 44 0 0 0 0 0 0 0 0 0 97 0 86 0 0 0 0 0 0 0 0 45 0 0 48 0 0 0 0 0 0 0 0 0 0 0 0 0 0 49 0 0 0 17 0 0 0 0 0 0 77 23 0 0 0 99 0 23 0 0 0 0 0 0 0 21 0 0 0 0 0 0 0 0 0 27 0 0 iU 22 So dE nD Vo CZ GW hj pp Wk tQ rl SZ YV Dd qx ic hU uo Sf uR QA AP 0 0 94 0 0 0 0 37 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 12 0 0 31 0 0 89 0 75 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 35 0 39 88 33 0 0 0 0 0 0 0 0 0 39 0 94 0 0 0 0 0 86 93 0 0 0 0 0 0 0 0 0 0 0 0 0 17 0 0 0 0 0 90 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 82 0 0 0 0 0 0 12 0 0 0 0 0 0 88 0 0 0 0 57 97 0 82 0 0 0 30 0 0 0 15 0 0 0 90 0 33 54 0 0 0 0 0 0 0 0 0 0 0 10 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 48 0 0 0 0 0 82 0 16 0 0 0 63 0 0 0 0 0 0 0 11 0 0 43 93 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 23 0 0 0 0 0 0 0 0 0 0 31 0 0 0 0 0 0 52 19 0 0 0 0 0 18 0 0 0 54 0 0 0 0 0 0 0 88 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 29 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 46 0 0 0 0 0 70 0 0 0 0 0 0 0 0 66 0 0 0 0 0 82 74 0 0 0 0 0 0 0 0 0 99 0 0 0 0 0 0 0 0 0 0 0 0 0 90 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 95 0 0 0 0 0 0 0 0 64 0 0 0 0 0 0 0 67 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 28 0 0 0 0 0 0 0 0 85 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 64 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 93 0 0 0 0 0 0 0 0 0 0 0 0 0 0 QA 23 UZ wD kG aA mm TZ lo bm QD XK ch MI Jn Rn el CA aC Nm BU pa kU Gs oR 0 0 0 0 0 95 0 0 0 19 0 0 0 49 0 0 0 0 10 0 0 0 0 0 0 22 0 0 0 29 0 0 0 49 0 0 54 0 63 0 0 0 0 0 0 26 0 48 0 0 0 66 0 0 80 0 47 0 0 0 0 0 0 32 55 30 0 0 0 0 0 94 0 0 0 0 15 17 0 0 0 86 0 0 0 0 0 0 0 54 0 0 0 54 0 0 0 0 0 0 0 0 0 0 52 0 0 0 0 0 0 0 0 0 0 98 0 0 0 0 0 70 0 0 0 0 0 0 0 88 52 0 44 0 0 30 0 0 0 0 0 0 0 0 0 0 0 0 0 0 53 0 0 0 0 0 0 0 0 0 42 0 0 0 0 0 19 0 0 0 0 0 0 0 0 0 0 0 62 0 0 0 0 0 0 68 0 62 0 99 0 0 0 0 0 25 0 35 0 0 0 0 0 0 84 0 0 0 0 0 14 0 0 0 0 92 0 61 0 0 0 0 0 0 0 70 0 80 21 61 0 0 53 0 0 36 87 0 0 0 0 0 16 41 90 0 0 0 0 17 0 0 12 0 0 0 14 0 0 0 47 0 0 19 0 0 0 0 0 0 0 0 31 0 0 0 0 0 76 22 0 0 73 32 0 31 0 0 0 0 0 0 0 0 0 0 0 0 0 0 19 0 0 0 0 0 74 10 0 0 0 37 0 0 50 79 0 0 0 0 0 53 0 0 0 0 0 0 72 0 0 0 78 0 0 62 0 0 0 23 0 0 53 47 0 88 0 31 0 0 35 0 0 0 0 0 91 57 0 0 0 0 0 0 0 0 10 27 0 0 0 0 0 29 0 0 0 0 0 0 0 0 0 0 0 88 36 0 0 0 0 0 0 0 0 0 0 48 0 0 0 0 0 0 0 0 17 0 0 34 43 0 0 0 0 0 0 0 0 82 0 0 0 0 0 0 0 95 64 0 0 78 0 0 30 0 0 0 0 0 0 0 0 0 0 0 0 0 24 0 0 0 0 0 0 0 0 0 0 0 0 0 19 0 0 0 0 0 0 0 0 0 0 0 0 0 37 44 0 0 0 26 0 73 0 24 0 61 0 0 0 0 70 0 0 0 50 0 0 0 0 63 0 17 0 66 0 99 0 62 76 0 0 0 0 0 0 0 0 0 0 0 41 17 0 0 0 34 0 kG 24 Vs Zg dR JD Zq gD pF ff EH qk JA Qj xG Mh TJ mT qw Hp vK OQ IA SZ Jj Mn 0 17 0 0 0 0 75 0 0 0 0 23 0 0 0 62 0 96 0 0 0 0 0 0 0 0 0 0 0 0 0 0 47 88 0 0 0 0 0 0 0 0 0 93 12 0 0 95 24 10 0 0 0 58 0 0 82 0 0 0 0 98 0 0 51 0 0 0 0 0 0 0 0 0 36 0 0 0 0 0 0 0 0 26 0 0 0 0 0 0 0 0 0 80 10 0 0 76 0 52 0 83 75 49 0 0 0 0 0 0 0 57 22 0 0 0 0 38 0 16 0 0 0 0 71 0 0 0 0 0 0 0 0 0 87 0 0 0 0 0 0 92 32 0 0 0 0 0 0 99 0 0 0 0 0 60 0 46 0 37 0 0 13 0 0 0 0 0 0 71 88 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 45 0 0 0 0 0 0 70 22 0 0 0 0 0 0 0 0 0 0 53 0 46 0 0 0 0 0 0 0 48 80 0 0 70 0 0 0 0 0 0 0 81 0 24 0 0 0 0 0 0 41 0 0 0 0 80 0 0 0 67 56 0 0 0 0 0 0 74 0 0 75 0 0 0 0 0 0 0 0 95 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 65 0 0 0 0 0 30 0 0 0 0 73 0 0 0 0 0 0 0 0 0 0 0 0 0 0 22 18 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 39 0 0 0 0 0 0 38 27 0 0 0 20 0 0 0 0 27 0 51 0 0 0 0 0 0 0 0 0 0 0 0 0 47 0 0 51 0 0 0 0 0 0 0 0 39 0 0 0 0 0 0 0 0 0 0 22 0 0 0 0 0 0 99 80 0 0 0 0 17 0 0 0 0 0 0 0 0 86 0 0 0 0 58 0 42 47 0 0 23 78 71 46 0 39 56 0 0 24 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 12 58 79 49 0 0 0 0 0 0 10 0 0 0 0 0 25 0 0 87 0 98 0 0 0 0 0 0 0 0 77 0 0 32 0 0 0 0 0 0 0 0 0 0 0 0 71 0 87 0 0 0 0 0 40 74 0 0 64 0 0 19 0 0 0 0 0 0 0 0 0 0 88 0 26 92 0 91 47 0 91 0 0 0 0 0 0 0 90 0 0 0 28 0 75 0 0 0 0 0 0 19 89 0 0 33 0 0 84 51 66 0 0 0 0 0 vK

输出样例2

ys-Hv-195----[ys Rc uf oR Hv ] ys-FM-83----[ys Rc FM ] ys-uA-144----[ys Xz bb uA ] ys-uf-123----[ys Rc uf ] ys-wK-255----[ys Ll sr wK ] ys-sJ-248----[ys Xz bb Nf sJ ] ys-Ll-61----[ys Ll ] ys-Xz-80----[ys Xz ] ys-Rc-48----[ys Rc ] ys-dj-163----[ys Rc uf dj ] ys-UP-139----[ys Rc UP ] ys-IP-278----[ys Rc FM WL Yq IP ] ys-sr-155----[ys Ll sr ] ys-Nf-189----[ys Xz bb Nf ] ys-Jx-32----[ys Jx ] ys-Mn--1 ys-eA--1 ys-WL-174----[ys Rc FM WL ] ys-ek-230----[ys Ll sr ek ] ys-bb-121----[ys Xz bb ] ys-Yq-259----[ys Rc FM WL Yq ] ys-dz--1 ys-oR-155----[ys Rc uf oR ] HI-NO-78----[HI kv FX yk NO ] HI-Kh-38----[HI Kh ] HI-LZ-72----[HI kv FX LZ ] HI-mu-56----[HI fO Uw mu ] HI-Uw-46----[HI fO Uw ] HI-FX-48----[HI kv FX ] HI-Jj-64----[HI NX Jj ] HI-Jn-47----[HI Jn ] HI-NX-52----[HI NX ] HI-FD-79----[HI fO Uw mu FD ] HI-uC-89----[HI fO Uw mu uC ] HI-fO-21----[HI fO ] HI-Kp-82----[HI kv FX LZ Kp ] HI-gY-66----[HI fO Uw gY ] HI-lm-65----[HI Jn lm ] HI-yk-58----[HI kv FX yk ] HI-sS-66----[HI sS ] HI-bu-70----[HI fO Uw bu ] HI-tB-59----[HI kv FX tB ] HI-MG-62----[HI fO MG ] HI-yP-63----[HI Jn yP ] HI-kv-17----[HI kv ] HI-is-55----[HI fO is ] yA-xS-194----[yA zG ah lV BN xS ] yA-FA-107----[yA Bw FA ] yA-jT-98----[yA jT ] yA-uu-94----[yA zG uu ] yA-BH-105----[yA zG BH ] yA-Ze-139----[yA Bw FA Ze ] yA-Zg-96----[yA zG ah lV Zg ] yA-zG-48----[yA zG ] yA-Bw-45----[yA Bw ] yA-nO-123----[yA jT nO ] yA-iJ-154----[yA Bw cG bA iJ ] yA-bA-123----[yA Bw cG bA ] yA-ff-159----[yA Bw FA ff ] yA-BN-144----[yA zG ah lV BN ] yA-cG-99----[yA Bw cG ] yA-lV-81----[yA zG ah lV ] yA-ZL-85----[yA zG ah ZL ] yA-ah-65----[yA zG ah ] yA-mP-117----[yA zG ah lV mP ] yA-TS-212----[yA Bw FA Ze TS ] yA-Jh-118----[yA zG ah ZL Jh ] SH-Cq-87----[SH Ay eH Cq ] SH-em-146----[SH dO em ] SH-Ay-10----[SH Ay ] SH-uA-79----[SH uA ] SH-eH-43----[SH Ay eH ] SH-Tq-67----[SH Ay Tq ] SH-yd-129----[SH dO kl yd ] SH-nY-77----[SH dO kl nY ] SH-Nz-144----[SH dO Nz ] SH-nm-139----[SH dO kl uv nm ] SH-kl-61----[SH dO kl ] SH-yu-121----[SH Ay eH Sb yu ] SH-eR-101----[SH Ay Tq eR ] SH-UH-89----[SH Ay UH ] SH-YP-122----[SH Ay eH Cq YP ] SH-FB-121----[SH dO FB ] SH-gs-104----[SH Ay eH Sb gs ] SH-MB-111----[SH uA MB ] SH-dO-50----[SH dO ] SH-Sb-83----[SH Ay eH Sb ] SH-uv-104----[SH dO kl uv ] SH-aO-142----[SH Ay UH aO ] SH-uf-191----[SH dO kl yd uf ] SH-gu-102----[SH uA gu ] Yz-kd-90----[Yz uJ Zs nf kd ] Yz-di-18----[Yz di ] Yz-Da-64----[Yz di Da ] Yz-Cz-43----[Yz Cz ] Yz-Rw-31----[Yz Rw ] Yz-Zs-33----[Yz uJ Zs ] Yz-jt-14----[Yz jt ] Yz-of-46----[Yz jt of ] Yz-nf-63----[Yz uJ Zs nf ] Yz-QP-47----[Yz uJ QP ] Yz-wq-64----[Yz di wq ] Yz-tZ-48----[Yz di tZ ] Yz-AY-99----[Yz jt MW AY ] Yz-MW-30----[Yz jt MW ] Yz-Py-74----[Yz jt MW Py ] Yz-ZK-71----[Yz jt ZK ] Yz-TD-75----[Yz uJ Zs nf TD ] Yz-uJ-17----[Yz uJ ] Yz-Ew-48----[Yz uJ Zs Ew ] Wg-wm-42----[Wg bQ wm ] Wg-bQ-18----[Wg bQ ] Wg-Er-90----[Wg Er ] Wg-OY-116----[Wg oI OY ] Wg-od-162----[Wg PS Ew od ] Wg-xz-213----[Wg PS eV Bc xz ] Wg-jN-100----[Wg bQ wm jN ] Wg-PS-35----[Wg PS ] Wg-eV-110----[Wg PS eV ] Wg-LF-106----[Wg bQ wm LF ] Wg-Yr-97----[Wg PS yd Yr ] Wg-Dk-104----[Wg Er Dk ] Wg-cN-151----[Wg Er cN ] Wg-cq-91----[Wg PS Ew cq ] Wg-WV-154----[Wg bQ wm LF WV ] Wg-Ew-65----[Wg PS Ew ] Wg-dn-109----[Wg PS yd dn ] Wg-uF-132----[Wg bQ wm LF uF ] Wg-yd-69----[Wg PS yd ] Wg-oI-61----[Wg oI ] Wg-Bc-156----[Wg PS eV Bc ] AA-qL-103----[AA Ox qL ] AA-kN-107----[AA Ox xB kN ] AA-fx-114----[AA Ox QQ fx ] AA-wz-39----[AA Ox wz ] AA-Qe-59----[AA Ox Qe ] AA-bS-60----[AA Ge bS ] AA-MP-26----[AA MP ] AA-xB-68----[AA Ox xB ] AA-Ox-19----[AA Ox ] AA-LY-70----[AA Qg LY ] AA-xY-73----[AA Ge xY ] AA-ds-119----[AA Ox qL ds ] AA-fC--1 AA-Ge-35----[AA Ge ] AA-Qg-58----[AA Qg ] AA-xr-80----[AA Ge xr ] AA-kR-41----[AA MP kR ] AA-EM-33----[AA Ox EM ] AA-QF-111----[AA MP QF ] AA-oY-60----[AA Ox oY ] AA-QQ-44----[AA Ox QQ ] KJ-iW-147----[KJ ma iW ] KJ-OV-117----[KJ my Aw OV ] KJ-xm-168----[KJ my pB iM xm ] KJ-ma-87----[KJ ma ] KJ-pB-74----[KJ my pB ] KJ-sA-160----[KJ my cn sA ] KJ-EK-80----[KJ my EK ] KJ-qD-139----[KJ my Aw OV qD ] KJ-Aw-96----[KJ my Aw ] KJ-cn-102----[KJ my cn ] KJ-my-64----[KJ my ] KJ-Kg-115----[KJ my cn Kg ] KJ-nP-152----[KJ ma nP ] KJ-zN-136----[KJ my pB gu zN ] KJ-zK-186----[KJ my Aw OV qD zK ] KJ-Nn-136----[KJ my cn Kg Nn ] KJ-gu-101----[KJ my pB gu ] KJ-JH-144----[KJ my Aw JH ] KJ-sX-169----[KJ ma sX ] KJ-Od-121----[KJ my Od ] KJ-Mm-125----[KJ my pB gu Mm ] KJ-iM-87----[KJ my pB iM ] KJ-wQ-142----[KJ my Aw wQ ] Dt-kp-99----[Dt ln zf kp ] Dt-QJ-79----[Dt OS XY QJ ] Dt-jw-86----[Dt jw ] Dt-Si-64----[Dt ln of cg Si ] Dt-MU-70----[Dt ln of MU ] Dt-cg-49----[Dt ln of cg ] Dt-td-90----[Dt ln of cg td ] Dt-Bq-78----[Dt ln qQ Bq ] Dt-qQ-50----[Dt ln qQ ] Dt-of-38----[Dt ln of ] Dt-hW-53----[Dt ln hW ] Dt-XY-69----[Dt OS XY ] Dt-kA-53----[Dt ln kA ] Dt-ld-36----[Dt yj ld ] Dt-EY-106----[Dt jw EY ] Dt-jL-103----[Dt yj jL ] Dt-zf-45----[Dt ln zf ] Dt-OS-58----[Dt OS ] Dt-Ua-74----[Dt ln of cg Ua ] Dt-nS-71----[Dt ln of cg nS ] Dt-yj-24----[Dt yj ] Dt-ln-18----[Dt ln ] Dt-lw-138----[Dt OS lw ] Lj-xh-30----[Lj xh ] Lj-xO-58----[Lj xh xO ] Lj-TO-52----[Lj TO ] Lj-Tc-92----[Lj ei Tc ] Lj-ZR-72----[Lj xh kI ZR ] Lj-iN-65----[Lj VN iN ] Lj-ei-25----[Lj ei ] Lj-Jo-68----[Lj ei Jo ] Lj-Gj-37----[Lj BP Gj ] Lj-ut-82----[Lj xh kI ut ] Lj-Ed-63----[Lj Ed ] Lj-bu-44----[Lj BP bu ] Lj-kI-40----[Lj xh kI ] Lj-BP-20----[Lj BP ] Lj-DK-73----[Lj Ed DK ] Lj-VN-50----[Lj VN ] Lj-rj-49----[Lj rj ] Lj-TH-54----[Lj xh kI TH ] Lj-WU-58----[Lj BP WU ] Lj-Bw-51----[Lj BP Bw ] Lj-XL-92----[Lj BP XL ] Lj-oC-45----[Lj xh oC ] iU-dj-156----[iU Xk OT jl kc aF dj ] iU-BK-189----[iU Pw lD BK ] iU-Ce-113----[iU aw Ce ] iU-jl-115----[iU Xk OT jl ] iU-re-97----[iU Xk re ] iU-OT-103----[iU Xk OT ] iU-uL-127----[iU aw km uL ] iU-aF-145----[iU Xk OT jl kc aF ] iU-aw-42----[iU aw ] iU-XG-173----[iU aw eq XG ] iU-kc-135----[iU Xk OT jl kc ] iU-VM-137----[iU Pw VM ] iU-eq-139----[iU aw eq ] iU-RV-193----[iU Xk OT jl kc aF RV ] iU-Pw-88----[iU Pw ] iU-fj-140----[iU Xk OT jl fj ] iU-lD-137----[iU Pw lD ] iU-Xk-71----[iU Xk ] iU-JN-272----[iU Xk OT jl kc aF RV JN ] iU-km-108----[iU aw km ] iU-Hq-89----[iU Xk Hq ] iU-XT-142----[iU aw Ce XT ] iU-ZN-144----[iU Xk ZN ] QA-So-132----[QA hj rl So ] QA-dE--1 QA-nD-184----[QA hj SZ nD ] QA-Vo-164----[QA hj rl Vo ] QA-CZ-214----[QA hj rl CZ ] QA-GW-152----[QA hj GW ] QA-hj-64----[QA hj ] QA-pp-169----[QA hj rl So pp ] QA-Wk-258----[QA hj rl Vo Wk ] QA-tQ-212----[QA hj uo YV tQ ] QA-rl-121----[QA hj rl ] QA-SZ-161----[QA hj SZ ] QA-YV-158----[QA hj uo YV ] QA-Dd-146----[QA hj Dd ] QA-qx-207----[QA hj rl So pp Sf qx ] QA-ic-257----[QA hj rl Vo ic ] QA-hU-223----[QA hj SZ nD hU ] QA-uo-94----[QA hj uo ] QA-Sf-179----[QA hj rl So pp Sf ] QA-uR--1 QA-AP-79----[QA hj AP ] kG-UZ-132----[kG Nm CA Gs UZ ] kG-wD-48----[kG wD ] kG-aA-68----[kG pa MI aA ] kG-mm-120----[kG Nm CA Gs mm ] kG-TZ-66----[kG TZ ] kG-lo-77----[kG wD lo ] kG-bm-83----[kG pa MI aA bm ] kG-QD-80----[kG QD ] kG-XK-94----[kG ch Jn XK ] kG-ch-47----[kG ch ] kG-MI-54----[kG pa MI ] kG-Jn-63----[kG ch Jn ] kG-Rn-88----[kG ch Rn ] kG-el-119----[kG BU el ] kG-CA-49----[kG Nm CA ] kG-aC-100----[kG ch oR aC ] kG-Nm-32----[kG Nm ] kG-BU-55----[kG BU ] kG-pa-30----[kG pa ] kG-kU-76----[kG Nm CA Gs kU ] kG-Gs-59----[kG Nm CA Gs ] kG-oR-59----[kG ch oR ] vK-Vs-71----[vK Vs ] vK-Zg-46----[vK Zg ] vK-dR-75----[vK JD dR ] vK-JD-39----[vK JD ] vK-Zq-56----[vK Zq ] vK-gD-118----[vK ff OQ TJ gD ] vK-pF-75----[vK JD Jj pF ] vK-ff-24----[vK ff ] vK-EH-93----[vK Zg EH ] vK-qk-91----[vK Zq Mn qk ] vK-JA-96----[vK JD Jj JA ] vK-Qj-65----[vK JD Qj ] vK-xG-117----[vK ff OQ TJ xG ] vK-Mh-90----[vK Zg IA Mh ] vK-TJ-79----[vK ff OQ TJ ] vK-mT-112----[vK JD Jj pF mT ] vK-qw-78----[vK Zq qw ] vK-Hp-99----[vK ff OQ TJ Hp ] vK-OQ-69----[vK ff OQ ] vK-IA-58----[vK Zg IA ] vK-SZ-94----[vK Zq SZ ] vK-Jj-49----[vK JD Jj ] vK-Mn-72----[vK Zq Mn ]

AC代码

#include <iostream>
#include<vector>
using namespace std;
const int max_vertex_number=100;
class Map{
    int matrix[max_vertex_number][max_vertex_number];
    int distance[max_vertex_number]={0};
    int vertex_number;
    string vertex[max_vertex_number];
    vector<int> path[max_vertex_number];
    string start;
    bool done[max_vertex_number]={false};
public:
    Map(){
        cin>>vertex_number;
        for(int i=0;i<vertex_number;i++)
            cin>>vertex[i];
        for(int i=0;i<vertex_number;i++)
            for(int j=0;j<vertex_number;j++)
                cin>>matrix[i][j];
        cin>>start;
    }
    void Dijkstra(){
        int startIndex= getIndex(start);
        for(int i=0;i<vertex_number;i++){
            if(matrix[startIndex][i]){
                distance[i]=matrix[startIndex][i];
                path[i].push_back(startIndex);
                path[i].push_back(i);
            }
        }
        done[startIndex]=true;
        for(int i=0;i<vertex_number-1;i++){
            int minDistance=0x3f3f3f3f;
            int minIndex;
            for(int j=0;j<vertex_number;j++)
                if(done[j]== false&&distance[j]&&distance[j]<minDistance){
                    minIndex=j;
                    minDistance=distance[j];
                }
            done[minIndex]=true;
            for(int j=0;j<vertex_number;j++)
                if(matrix[minIndex][j]&&done[j]== false&&(minDistance+matrix[minIndex][j]<distance[j]||distance[j]==0)){
                    distance[j]=minDistance+matrix[minIndex][j];
                    path[j]=path[minIndex];
                    path[j].push_back(j);
                }
        }
    }
    int getIndex(string&data){
        for(int i=0;i<vertex_number;i++)
            if(data==vertex[i])
                return i;
    }
    void Show(){
        Dijkstra();
        for(int i=0;i<vertex_number;i++){
            if(i== getIndex(start))
                continue;
            if(distance[i]){
                cout<<start<<'-'<<vertex[i]<<'-'<<distance[i]<<"----[";
                for(auto&it:path[i])
                    cout<<vertex[it]<<' ';
                cout<<"]\n";
            }else cout<<start<<'-'<<vertex[i]<<"--1"<<endl;
        }
    }
};
int main() {
    int t;
    cin>>t;
    while(t--){
        Map test;
        test.Show();
    }
}