城市交通路网

题目描述

城市编号1..N。费用矩阵表示有向道路，正数为费用，0表示无道路，对角线为0。求城市1到城市N的最少费用，并给出最短路径；如有多条最短路径，选顶点编号序列字典序最小的一条。

输入

第一行N，1≤N≤200；随后N行，每行N个整数，0≤w[i][j]≤10^9，对角线0。道路费用严格为正。

输出

无法到达时仅输出minlong=-1。否则第一行minlong=最少费用，第二行依次输出从1到N的路径顶点。N=1时费用0、路径为1。

输入样例

10
0 2 5 1 0 0 0 0 0 0
0 0 0 0 12 14 0 0 0 0
0 0 0 0 6 10 4 0 0 0
0 0 0 0 13 12 11 0 0 0
0 0 0 0 0 0 0 3 9 0
0 0 0 0 0 0 0 6 5 0
0 0 0 0 0 0 0 0 10 0
0 0 0 0 0 0 0 0 0 5
0 0 0 0 0 0 0 0 0 2
0 0 0 0 0 0 0 0 0 0

输出样例

minlong=19
1 3 5 8 10

本地补充约定

明确为正权有向矩阵图，既输出费用又输出路径、并列取字典序最小；不依赖缺失图片、不限定必须编号拓扑有序。

本题使用独立构造并核验的训练数据，非官方原版数据。

本地修订与来源

本题为经授权补全的本地训练修订版，原始公开题面保留在采集档案；修订了：明确为正权有向矩阵图，既输出费用又输出路径、并列取字典序最小；不依赖缺失图片、不限定必须编号拓扑有序。。此处题意、范围和输出约定以本修订版为准，不冒称原站或官方原版。原题链接：https://ybt.ssoier.cn/problem_show.php?pid=1261。

评测数据说明

本题使用按题意独立构造、以独立程序核对的训练数据及公开样例，共5个测试点，非原站或官方原始数据。总分100分。