← 返回题目

题库练习传令兵

← 上一题下一题 →

A71378 | $传令兵$

来源编程题

时间限制1s

内存限制512MB

通过 / 提交0/0

题目描述

A国的边境上修建了 n 座兵营（编号为 1 \sim n ），某些兵营之间修建了用于传达消息的双向道路，不同的道路由于长度和平整度不同，也就可能需要不同的天数才能走完。 为方便指挥作战，A国将指挥所修建在了 1 号兵营。当指挥部下达作战指令后，指挥部就派出若干个传令兵，按照预先修好的道路，将指令传达给相邻的兵营。当一座兵营接到指令后，会按同样的方式向其他兵营传达指令，直到所有的兵营都收到作战指令。 请编程计算出，从指挥部发出作战指令到所有兵营都收到作战命令，最短需要多少天。

输入格式

第一行有两个整数 n 和 m ，表示有 n 个兵营和 m 条道路。 第 2 至 m+1 行，每行三个整数 x, y, k ，表示第 x 个和第 y 个兵营之间存在一条需要 k 天才能走完的双向道路。 本题数据保证任意两个兵营之间最多只有一条道路。

输出格式

输出所有兵营接到指令的最短天数，如果由于道路的缺失，导致无论如何都不能做到所有兵营都能接到指令，请输出 -1 。

输入输出样例

输入 #1

输出 #1

C++ 编辑器

输入

输出