题目描述

某公司于乙城市的销售点急需一批成品，该公司成品生产基地在甲城市。 甲城市与乙城市之间共有 nn 座城市，互相以公路连通。
甲城市、乙 城市以及其它各城市之间的公路连通情况及每段公路的长度由 矩阵 m1m_1 给出。 每段公路均由地方政府收取不同额度的养路费等费用，具体数额由矩阵 m2m_2 给出。
请给出在需付养路费总额不超过 15001500 的情况下，该公司货车运送其产品从甲城市到乙城市的最短运送路线。

甲城市为 00 号城市，乙城市为 n−1n-1 号城市。

示例

输入

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
n=50
m1 = [
  [-1,38,28,48,70,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,],
  [-1,-1,-1,-1,-1,46,59,68,44,-1,-1,-1,116,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,],
  [-1,-1,-1,-1,-1,50,48,42,59,-1,-1,121,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,],
  [-1,-1,-1,-1,-1,75,57,78,40,-1,126,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,],
  [-1,-1,-1,-1,-1,46,43,53,39,133,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,],
  [-1,-1,-1,-1,2,-1,-1,-1,-1,38,61,35,36,-1,-1,-1,127,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,],
  [-1,-1,-1,7,-1,-1,-1,-1,-1,73,75,57,36,-1,-1,133,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,],
  [-1,-1,8,-1,-1,-1,-1,-1,-1,36,33,30,61,-1,123,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,],
  [-1,3,-1,-1,-1,-1,-1,-1,-1,61,65,53,78,125,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,],
  [-1,-1,-1,-1,-1,-1,-1,-1,8,-1,-1,-1,-1,58,45,41,48,-1,-1,-1,135,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,],
  [-1,-1,-1,-1,-1,-1,-1,2,-1,-1,-1,-1,-1,74,32,76,36,-1,-1,116,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,],
  [-1,-1,-1,-1,-1,-1,4,-1,-1,-1,-1,-1,-1,28,74,70,54,-1,123,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,],
  [-1,-1,-1,-1,-1,2,-1,-1,-1,-1,-1,-1,-1,51,65,42,29,132,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,],
  [-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,7,-1,-1,-1,-1,56,78,74,38,-1,-1,-1,130,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,],
  [-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,4,-1,-1,-1,-1,-1,74,74,40,34,-1,-1,126,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,],
  [-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,7,-1,-1,-1,-1,-1,-1,50,55,49,74,-1,127,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,],
  [-1,-1,-1,-1,-1,-1,-1,-1,-1,4,-1,-1,-1,-1,-1,-1,-1,36,60,74,39,130,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,],
  [-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,3,-1,-1,-1,-1,29,38,68,40,-1,-1,-1,126,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,],
  [-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,4,-1,-1,-1,-1,-1,70,46,60,45,-1,-1,125,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,],
  [-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,4,-1,-1,-1,-1,-1,-1,36,62,57,43,-1,127,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,],
  [-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,4,-1,-1,-1,-1,-1,-1,-1,65,29,53,69,122,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,],
  [-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,4,-1,-1,-1,-1,58,54,75,53,-1,-1,-1,121,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,],
  [-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,3,-1,-1,-1,-1,-1,42,72,54,75,-1,-1,136,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,],
  [-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,6,-1,-1,-1,-1,-1,-1,63,34,43,60,-1,120,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,],
  [-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,3,-1,-1,-1,-1,-1,-1,-1,68,45,71,38,127,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,],
  [-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,4,-1,-1,-1,-1,58,34,43,69,-1,-1,-1,130,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,],
  [-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,8,-1,-1,-1,-1,-1,73,63,75,49,-1,-1,121,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,],
  [-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,5,-1,-1,-1,-1,-1,-1,69,54,34,68,-1,122,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,],
  [-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,5,-1,-1,-1,-1,-1,-1,-1,54,30,47,41,122,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,],
  [-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,2,-1,-1,-1,-1,59,44,52,57,-1,-1,-1,121,-1,-1,-1,-1,-1,-1,-1,-1,-1,],
  [-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,3,-1,-1,-1,-1,-1,74,50,66,58,-1,-1,136,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,],
  [-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,3,-1,-1,-1,-1,-1,-1,36,54,69,33,-1,130,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,],
  [-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,6,-1,-1,-1,-1,-1,-1,-1,51,41,66,62,118,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,],
  [-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,3,-1,-1,-1,-1,63,56,35,76,-1,-1,-1,120,-1,-1,-1,-1,-1,],
  [-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,8,-1,-1,-1,-1,-1,42,56,71,64,-1,-1,123,-1,-1,-1,-1,-1,-1,],
  [-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,2,-1,-1,-1,-1,-1,-1,28,44,40,61,-1,130,-1,-1,-1,-1,-1,-1,-1,],
  [-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,4,-1,-1,-1,-1,-1,-1,-1,33,28,58,72,116,-1,-1,-1,-1,-1,-1,-1,-1,],
  [-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,4,-1,-1,-1,-1,63,65,42,56,-1,-1,-1,118,-1,],
  [-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,2,-1,-1,-1,-1,-1,63,66,50,40,-1,-1,117,-1,-1,],
  [-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,5,-1,-1,-1,-1,-1,-1,59,41,34,66,-1,132,-1,-1,-1,],
  [-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,3,-1,-1,-1,-1,-1,-1,-1,66,48,28,42,134,-1,-1,-1,-1,],
  [-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,8,-1,-1,-1,-1,50,29,70,62,-1,],
  [-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,8,-1,-1,-1,-1,-1,34,31,55,59,-1,],
  [-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,3,-1,-1,-1,-1,-1,-1,61,30,73,43,-1,],
  [-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,4,-1,-1,-1,-1,-1,-1,-1,77,30,63,33,-1,],
  [-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,7,-1,-1,-1,-1,43,],
  [-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,2,-1,-1,-1,-1,-1,50,],
  [-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,4,-1,-1,-1,-1,-1,-1,30,],
  [-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,3,-1,-1,-1,-1,-1,-1,-1,56,],
  [-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,],
]

m2 = [
  [33,117,73,22,131,108,28,150,87,108,33,51,101,28,70,38,100,194,178,177,117,89,48,95,176,168,35,165,102,159,167,182,94,25,79,159,183,167,96,119,185,57,190,195,133,52,23,50,141,15,],
  [32,66,200,72,62,55,177,61,115,22,103,10,109,180,147,119,199,155,84,141,178,130,136,68,137,132,101,177,126,182,85,147,154,58,39,179,124,185,158,198,134,107,141,22,86,138,188,21,122,90,],
  [29,144,182,27,161,57,108,39,150,12,172,111,91,188,149,78,104,183,153,112,178,35,59,10,47,105,25,13,68,181,192,152,160,60,191,119,69,175,69,120,151,22,135,174,22,80,82,188,138,75,],
  [56,13,18,68,158,176,21,114,162,127,28,100,153,77,28,29,187,76,103,193,158,165,192,86,167,76,49,187,65,120,149,192,150,97,150,166,189,134,150,58,154,192,22,193,52,25,96,113,174,188,],
  [195,25,74,16,22,66,85,123,75,172,181,79,198,109,74,48,23,89,153,62,30,63,44,120,94,134,139,111,187,44,194,102,104,34,197,175,98,107,42,93,149,69,46,37,21,160,184,165,18,88,],
  [184,24,76,154,54,44,163,99,20,58,151,99,124,158,123,162,41,78,188,189,15,125,103,101,58,165,133,151,70,35,189,85,42,70,158,181,103,18,187,44,189,124,196,14,62,129,129,184,35,59,],
  [98,61,125,17,172,177,55,72,64,12,159,144,64,189,91,104,199,146,60,191,63,120,165,50,85,116,67,79,179,64,136,24,165,43,145,104,80,155,46,149,40,39,122,168,81,37,130,20,49,191,],
  [29,189,97,167,116,180,112,172,77,103,122,200,165,187,151,167,164,178,173,46,153,20,108,50,186,103,176,148,143,77,46,43,171,119,156,70,174,156,45,31,115,38,127,78,135,85,26,79,33,82,],
  [157,115,65,70,165,62,40,138,66,191,62,171,133,151,18,130,111,179,179,193,122,140,72,26,144,57,50,70,147,43,68,85,41,21,134,173,164,138,58,115,29,84,126,112,165,195,197,118,136,164,],
  [164,147,22,103,119,160,159,12,58,187,174,171,67,83,89,62,33,43,69,170,72,194,105,54,116,40,32,190,129,29,152,115,132,66,122,200,13,184,96,108,192,65,173,43,14,104,49,119,176,136,],
  [187,171,79,14,117,196,105,100,117,65,196,82,12,63,109,21,33,71,16,15,48,181,172,170,92,159,97,71,44,99,73,163,64,105,92,113,184,177,25,11,62,172,92,149,81,157,116,175,57,91,],
  [152,14,79,52,47,145,66,40,200,74,196,38,104,40,162,47,182,39,99,143,98,111,15,83,128,156,180,160,167,125,117,66,170,181,118,78,148,37,130,57,16,198,48,161,165,148,154,33,16,195,],
  [91,18,36,75,178,93,61,162,21,69,149,40,40,85,83,89,100,182,169,38,154,197,111,138,172,97,101,21,85,162,162,115,194,151,197,65,38,161,68,14,100,161,186,21,77,22,173,196,113,13,],
  [129,103,165,191,25,52,72,107,104,198,118,10,153,65,55,191,55,190,44,157,146,198,132,175,86,121,173,195,68,35,190,51,61,31,139,151,161,114,34,22,196,192,133,39,91,190,170,197,119,83,],
  [110,181,47,80,149,81,76,126,111,39,73,52,192,83,55,93,41,191,191,188,101,79,148,148,30,82,176,67,76,198,165,31,103,122,192,111,11,30,40,110,43,118,77,57,21,51,169,41,127,136,],
  [11,116,68,43,43,19,66,152,106,35,143,80,27,125,69,12,73,109,139,182,97,49,45,199,129,155,41,55,94,195,22,37,28,29,194,181,106,140,31,199,89,65,142,21,160,151,159,66,107,23,],
  [195,89,39,180,65,76,113,91,51,46,131,73,68,40,12,75,199,56,21,60,80,182,191,49,166,114,80,137,165,91,31,74,119,171,196,148,153,114,85,104,164,193,91,134,54,169,167,94,156,134,],
  [145,120,50,11,60,73,192,132,160,95,94,51,74,88,131,55,188,186,118,64,149,25,193,151,163,173,144,164,133,122,83,130,198,178,190,161,173,186,98,131,198,27,36,81,64,113,138,128,162,183,],
  [111,119,52,175,195,88,115,196,145,16,119,30,60,183,37,77,72,69,97,57,164,11,91,34,43,22,182,27,144,137,119,70,39,54,72,163,178,101,131,67,93,128,194,52,195,175,104,184,22,174,],
  [53,93,178,94,22,94,123,107,129,111,28,155,179,75,103,197,191,24,182,133,67,121,179,172,126,106,46,79,160,151,131,106,152,182,199,79,104,138,171,54,21,158,62,62,167,30,132,82,174,58,],
  [192,188,171,91,157,14,43,114,134,132,64,144,65,103,42,26,177,114,73,67,95,15,18,57,89,194,50,88,157,138,119,34,38,69,96,69,180,54,138,110,161,160,117,198,198,103,166,150,164,115,],
  [53,64,187,180,55,154,120,138,148,191,146,129,104,89,33,92,145,88,55,126,37,165,31,164,143,173,29,194,47,35,84,37,89,133,86,190,62,32,18,10,186,81,106,59,22,113,166,74,99,166,],
  [134,88,170,79,187,11,23,31,100,169,129,98,23,76,40,84,116,149,65,129,170,181,30,142,48,93,131,69,198,122,189,199,104,199,167,37,10,115,197,92,43,125,53,111,177,127,19,95,152,94,],
  [45,136,165,81,141,122,49,102,139,97,198,62,99,188,31,128,129,17,165,108,94,93,60,165,127,91,152,11,52,60,104,108,53,129,125,130,88,26,145,174,80,128,96,50,20,139,76,158,191,135,],
  [52,58,61,75,91,92,11,88,187,92,102,157,47,162,69,67,147,145,38,57,158,47,81,127,29,139,104,93,15,20,157,131,28,46,13,18,117,169,138,160,138,26,157,196,189,92,198,195,167,178,],
  [102,78,89,47,56,172,75,95,176,136,108,128,164,69,143,32,122,168,148,40,93,199,116,16,51,79,21,89,16,93,65,133,160,173,179,126,142,160,32,29,86,200,62,115,98,163,148,86,64,119,],
  [78,91,111,138,124,15,196,200,48,87,146,190,98,47,40,50,52,184,135,99,52,102,129,45,168,94,175,161,55,84,173,73,92,132,80,186,168,175,102,68,17,54,19,173,140,20,38,199,41,57,],
  [172,196,65,71,63,140,30,107,91,94,118,97,198,138,164,191,170,15,83,112,29,67,96,186,167,44,13,42,199,75,63,161,168,193,143,167,43,18,46,133,132,169,84,102,23,142,153,180,79,154,],
  [167,36,96,61,169,43,42,74,102,38,63,184,132,92,161,177,110,156,153,56,50,145,150,185,12,180,121,131,188,60,96,92,35,121,37,30,38,174,177,14,86,193,40,114,163,90,181,82,122,67,],
  [131,79,71,197,110,113,60,189,152,49,51,73,189,25,171,136,165,102,92,88,109,33,108,110,155,140,126,171,122,112,151,69,124,29,29,146,17,55,73,142,69,198,131,197,184,194,95,132,24,27,],
  [178,166,197,145,138,149,107,72,33,162,161,41,12,151,31,182,184,24,33,135,167,16,158,198,200,86,59,120,180,123,23,100,200,80,115,26,156,191,114,60,17,70,113,121,93,40,85,199,117,115,],
  [30,17,27,110,167,60,91,158,153,105,112,165,100,21,165,193,27,167,59,36,106,106,194,34,170,177,193,119,141,10,79,136,58,74,94,162,187,86,27,137,151,30,118,184,67,50,44,93,11,171,],
  [52,33,76,137,51,55,68,59,175,53,170,87,92,144,33,66,53,188,173,87,147,160,181,19,79,79,180,126,181,78,32,28,97,140,128,81,18,148,83,70,82,185,78,62,99,159,184,74,98,191,],
  [24,53,103,185,150,197,112,45,40,33,60,148,92,175,74,115,137,61,107,133,193,63,82,50,138,26,86,75,96,33,198,16,136,131,163,54,122,90,55,68,151,60,122,199,71,198,151,164,53,78,],
  [77,50,181,155,62,62,156,32,176,48,190,158,58,11,89,169,172,72,131,70,100,107,130,164,75,73,175,46,158,67,58,23,182,173,70,91,78,98,103,179,91,132,13,58,185,109,31,174,42,153,],
  [170,67,78,171,196,121,123,71,100,174,141,29,26,20,96,104,17,51,27,97,54,110,22,195,166,17,90,74,23,112,82,103,78,26,20,160,196,148,113,158,169,182,196,23,106,189,43,110,23,156,],
  [61,15,59,43,200,47,23,105,80,15,87,81,108,41,112,141,36,84,120,83,60,186,63,19,141,25,148,70,105,86,189,44,28,82,166,105,28,125,130,166,99,183,58,117,49,186,19,74,155,55,],
  [150,14,24,10,170,176,98,67,98,34,160,95,81,36,18,158,87,177,84,128,67,79,100,97,92,162,33,200,169,162,106,39,200,41,117,102,71,152,157,54,157,151,53,174,40,149,10,63,104,33,],
  [72,34,72,174,176,187,161,11,127,99,105,30,25,164,64,13,188,145,13,141,117,42,85,36,38,164,179,36,29,22,169,114,43,31,49,114,90,147,152,182,21,92,191,127,171,87,125,93,187,76,],
  [184,148,198,72,118,167,174,23,90,168,15,189,116,111,48,172,169,44,195,24,161,153,43,134,139,61,70,60,28,110,18,95,143,13,99,175,29,64,21,43,136,33,16,134,57,140,160,39,45,39,],
  [185,118,146,144,37,156,178,26,80,95,20,10,156,155,75,79,28,43,127,86,27,187,141,168,176,38,134,139,33,95,131,17,182,74,197,17,69,53,18,107,163,199,173,39,28,117,58,167,110,120,],
  [68,75,169,99,15,40,183,182,11,131,33,110,79,83,162,115,59,69,101,92,54,38,67,13,32,48,32,168,67,193,194,117,90,88,193,135,157,34,57,82,35,150,179,128,91,157,171,130,89,47,],
  [47,168,44,17,10,122,106,25,160,85,17,109,106,85,132,183,59,82,72,166,176,106,44,79,112,12,181,70,29,195,193,43,89,106,125,62,122,78,99,137,153,126,162,56,159,193,91,45,129,177,],
  [167,12,140,158,160,91,156,45,146,125,176,159,81,121,43,131,39,85,66,181,82,141,91,199,181,50,104,23,51,125,115,107,66,181,73,175,181,176,43,153,30,116,57,121,68,100,45,95,141,29,],
  [192,25,174,23,142,170,31,174,10,185,103,28,16,27,138,176,174,128,174,116,79,57,115,17,50,199,73,49,55,106,112,12,183,67,165,74,160,17,113,86,29,183,187,77,37,198,180,187,58,100,],
  [12,46,47,75,44,29,131,29,113,106,95,115,72,199,21,91,179,31,198,162,177,70,60,188,34,59,113,57,194,175,52,23,73,102,45,46,65,159,99,181,193,192,122,153,149,101,135,121,134,169,],
  [51,87,187,45,43,182,82,156,72,95,164,55,140,111,77,108,24,84,188,145,23,186,133,74,35,74,118,130,190,134,96,69,95,132,62,113,130,67,12,165,199,29,172,164,172,181,63,52,85,92,],
  [194,176,178,24,199,194,152,200,112,190,168,22,58,151,69,142,183,124,13,46,118,145,125,95,23,138,63,76,40,199,86,61,182,37,191,28,199,51,79,37,167,36,165,157,114,148,174,129,65,156,],
  [147,170,154,132,119,199,152,40,138,107,135,71,120,106,91,118,182,102,66,52,68,107,128,13,33,200,136,63,96,51,154,106,19,123,76,180,38,57,77,184,22,146,103,94,31,157,76,136,94,16,],
  [132,19,123,191,200,180,102,87,109,68,172,35,167,120,106,146,168,78,190,67,78,125,15,27,112,104,17,10,34,130,68,78,67,33,27,199,63,62,154,115,56,185,98,137,56,191,198,188,106,151,],
]

输出

1
2
3
path = [0, 2, 7, 10, 14, 20, 22, 25, 31, 36, 38, 44, 46, 49]
最短路径 = 464
养路费 = 1448

思路

符号说明

使用 min_distsmin\_dists 来表示每个城市到乙城市的最短路径，min_costsmin\_costs 来表示每个城市到乙城市的最小养路费。即 min_distsumin\_dists_u 表示编号为 uu 的城市到达终点(即城市乙)的最短距离。min_costsumin\_costs_u 表示编号为 uu 的城市到达终点的最小养路费，显然有 min_distsn−1=0min\_dists_{n-1} = 0，min_costsn−1=0min\_costs_{n-1} = 0。

我们用 distu,vdist_{u,v} 来表示城市 uu 到城市 vv 的最短距离，用 costu,vcost_{u, v} 来表示城市 uu 到城市 vv 的最小养路费。用 m1u,vm1_{u,v}来表示输入矩阵 m1m1 中第 uu 行第 vv 列的数据，用 m2u,vm2_{u,v}来表示输入矩阵 m2m2 中第 uu 行第 vv 列的数据。

最后，使用 min_distmin\_dist 来表示最终结果，即甲城市到乙城市在养路费不超过 15001500 的前提下的最短路径。

算法介绍

首先，使用 dijkstra 算法计算 min_distsmin\_dists 和 min_costsmin\_costs。这和传统的 dijkstra 算法没什么不同。

使用深度优先搜索算法和回溯算法来寻找最短路径。具体的方法是首先将最终结果 min_distmin\_dist 初始化为无穷大，然后使用深度优先搜索算法进行搜索，在搜索的过程中，计算搜索到当前城市时已经走过的距离和已经使用的养路费。当搜索到乙城市的时候，判断当前的养路费是否小于 min_distmin\_dist 。如果是，则更新 min_distmin\_dist。

在搜索过程中，需要使用剪枝算法以减少搜索量。具体方法为，当搜索到城市 uu 时，遍历所有与城市 uu 连通的城市 vv ，如果城市 vv 在本轮搜索中已经访问过，则忽略之，否则，计算如果通过城市 vv 前往乙城市可能的最短路径和最小养路费。这里不妨用 distudist_u 来表示搜索到城市 uu 时已经走过的距离，用 costucost_u 来表示搜索到城市 uu 时已经花费的养路费。那么，如果要通过城市 vv 前往城市乙，则最少还要走

possible_min_dist=distu+𝑚1u,v+min_distsvpossible\_min\_dist = dist_u + 𝑚1_{u,v} + min\_dists_v

的距离，同时至少还要花费

possible_min_cost=costu+𝑚2u,v+min_costsvpossible\_min\_cost = cost_u + 𝑚2_{u,v} + min\_costs_v

的养路费。那么，如果 possible_min_cost>1500possible\_min\_cost \gt 1500 或者 possible_min_dist>min_distpossible\_min\_dist > min\_dist，就可以剪枝，因为至少还要花费的养路费已经大于了 15001500，或者至少还要走的距离已经大于了之前计算的最小路径，没有必要再继续搜索了。

具体实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
#include <iostream>
#include <fstream>
#include <array>
#include <queue>
#include <cassert>


// 常量
const int n = 50;
const int m = 50;
const int inf = 0x3f3f3f3f;


using matrix = std::array<std::array<int, m>, n>;
using list = std::array<int, n>;


// 全局变量
matrix m1;
matrix m2;
std::array<bool, n> visit;
list path;
list result_path;
int min_dist;

list dijkstra(const matrix &graph, int end);
void dfs(const list &min_dists, const list &min_costs, int vex, int dist, int cost, int deep);

int main(int argc, const char **argv)
{
  // 读入两个矩阵
  std::ifstream stream;
  stream.open("./m1.txt");
  for (int i = 0; i < n; i++)
  {
    for (int j = 0; j < m; j++)
    {
      stream >> m1[i][j];
    }
  }
  stream.close();
  stream.open("./m2.txt");
  for (int i = 0; i < n; i++)
  {
    for (int j = 0; j < m; j++)
    {
      stream >> m2[i][j];
    }
  }
  stream.close();

  const int start = 0;
  const int end = n-1;
  auto min_dists = dijkstra(m1, end);
  auto min_costs = dijkstra(m2, end);

  // 不考虑养路费的前提下的最短路径
  std::cout << "The shortest path without considering the road maintenance fee:" << min_dists[start] << std::endl;

  visit.fill(false);
  min_dist = inf;
  path.fill(-1);

  dfs(min_dists, min_costs, start, 0, 0, 0);

  std::cout << "path: ";
  std::vector<int> path;
  for(auto x : result_path) {
    if(x == end) {
      std::cout << x+1 << std::endl;
      path.push_back(x);
      break;
    }
    else {
      path.push_back(x);
      std::cout << x+1 << " -> ";
    }
  }

  int total_dist = 0, total_cost = 0;
  for(int i=0; i<path.size()-1; i++) {
    int u = path[i];
    int v = path[i+1];
    total_dist += m1[u][v];
    total_cost += m2[u][v];
  }


  std::cout << "The shortest path with maintenance cost not exceeding 1500: " << total_dist << 
  "\nThe final cost of road maintenance: " << total_cost << std::endl;
}

struct State
{
  int id;
  int dist;

  bool operator<(const State &other) const
  {
    return dist > other.dist;
  }

  State(int id, int dist) : id(id), dist(dist) {}
};

list dijkstra(const matrix &graph, int end)
{
  list result;
  result.fill(inf);
  visit.fill(false);

  result[end] = 0;

  std::priority_queue<State> queue;
  queue.push(State(end, 0));

  while (!queue.empty())
  {
    auto top = queue.top();
    queue.pop();
    if (visit[top.id])
      continue;

    visit[top.id] = true;
    assert(result[top.id] == top.dist);
    for (int u = 0; u < n; u++)
    {
      if (graph[u][top.id] <= -1)
        continue;
      int w = top.dist + graph[u][top.id];
      if (w < result[u])
      {
        result[u] = w;
        assert(!visit[u]);
        queue.push(State(u, w));
      }
    }
  }

  return std::move(result);
}


void dfs(const list &min_dists, const list &min_costs, int vex, int dist, int cost, int deep) {
  
  path[deep] = vex;
  if(vex == n-1) {
    if(dist < min_dist) {
      min_dist = dist;
      result_path = path;
    }
    return;
  }
  
  visit[vex] = true;
  const int u = vex;
  for(int v=0; v < m; v++) {
    if(m1[u][v] <= -1 || visit[v]) continue;

    int possible_min_dist = dist + m1[u][v] + min_dists[v];
    int possible_min_cost = cost + m2[u][v] + min_costs[v];
    if(possible_min_cost > 1500 || possible_min_dist > min_dist) continue; // 剪枝
    dfs(min_dists, min_costs, v, dist + m1[u][v], cost + m2[u][v], deep+1);
  }
  visit[vex] = false;
}