A6179. Moving Both Hands
编程题
普及+/提高
知识点
题目描述
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$ 的有向边。
接下来 $m$行，每行三个整数 $u$，$v$，$w$，表示图上有一条从 $u$ 指向 $v$ 长为 $w$ 的有向边。
输出格式
输出一行 $n - 1$ 个整数，由空格隔开，第 $i$ 个整数表示蓝色球开始时在 $i$ 号点上时游戏的最小完成时间。如果不能完成游戏，输出 -1 。
输入输出样例
输入 #1
5 7 1 2 2 2 4 1 4 1 4 2 5 3 5 4 1 5 2 4 2 1 1
输出 #1
1 -1 3 4