A6179 | $Moving Both Hands$

时间限制1s

内存限制128MB

通过 / 提交0/0

题目描述

Alice 在进行一个有向图上做游戏。有向图上共有 $n$ 个节点，$m$ 条有向边。Alice的手上有一个红色球和一个蓝色球。游戏开始时，Alice将红色球放在 $1$ 号节点上，将蓝色球放在 $i$ 号节点上。长度为 $w$的有向边表示可以通过一次操作将在 $v$ 的点转移到 $u$ 花费 $w$ 时间。每局游戏中，Alice 要通过尽可能少的时间将两个球共同转移到任意同一个节点上。Alice 同一时间只能操作一个球。现在 Alice 想知道对于每个点 $2\le i \le n$，每局游戏完成的最小时间是多少。

输入第一行是两个整数 $n$ ，$m$。 接下来 $m$行，每行三个整数 $u$，$v$，$w$，表示图上有一条从 $u$ 指向 $v$ 长为 $w$ 的有向边。

输出一行 $n - 1$ 个整数，由空格隔开，第 $i$ 个整数表示蓝色球开始时在 $i$ 号点上时游戏的最小完成时间。如果不能完成游戏，输出 -1 。

输入 #1

输出 #1

1 -1 3 4

C++ 编辑器

输入

输出