← 返回题目

题库练习行路难

← 上一题下一题 →

A2175 | $行路难$

来源省选

时间限制1s

内存限制128MB

通过 / 提交0/0

题目描述

小X来到了山区，领略山林之乐。在他乐以忘忧之时，他突然发现，开学迫在眉睫 山区有 $n$ 座山。山之间有 $m$ 条羊肠小道，每条连接两座山，只能单向通过，并会耗费小 X 一定时间。 小 X 现在在 $1$ 号山，他的目的是 $n$ 号山，因为那里有火车站。 然而小 X 的体力是有限的。他每通过一条羊肠小道，就会变得更疲劳，导致他通过任意一条羊肠小道的时间都增加 $1$。

输入格式

第一行两个数，$n,m$。 第 $2$ 行到第 $m+1$ 行，每行 $3$ 个数 $A, B, C$，表示 $A$ 、 $B$ 之间有一条羊肠小道，可以让小 X 花费 $C$ 的时间从 $A$ 移动到 $B$。

输出格式

第一行一个数 $T$，表示小 X 需要的最短时间。 第二行若干个数，用空格隔开，表示小 X 的移动路线。例如，$[1, 4, 2, 5]$ 表示小 $X$ 从 $1$ 号山开始，移动到 $4$ 号山，再到 $2$ 号山，最后到 $5$ 号山。

输入输出样例

输入 #1

输出 #1

7
1 3 5

C++ 编辑器

输入

输出