乌鸦坐飞机
Time Limit: 15000 ms
Memory Limit: 65536 KiB
Problem Description
传说中的乌鸦(阿福)今天准备去一个神秘的地方进行一些不 (xie) 为 (e) 人 (zhi) 知 (ji) 的 py 交易。~~(喂!,如果是乌鸦的话为什么还要坐飞机啊)~~只不过这货已经是懒癌晚期了,她决定放出她的大招,乌鸦坐飞机!
阿福看到(世界?)地图上有 $n$ 个城市,城市之间有 $m$ 条道路,每条道路花费的时间不同。现在阿福想要从当前的 $s$ 城市出发到达 $t$ 城市,进行交易,如今阿福已经是失去理性的英灵了,你能帮帮她找出花费时间最少的道路么?
Input
第一行输入两个以空格分隔的整数 $n$, $m$。表示地图上一共有 $n$ 个城市,$m$ 条边。
$(2 \leqslant n \leqslant 1000, 0 \leqslant m \leqslant 100000)$
接下来输入 $m$ 行,每行 $3$ 个整数 $u$, $v$, $w$ 表示 $u$ 和 $v$ 之间有一条道路,花费的时间为 $w$。
$(1 \leqslant u, v \leqslant n, 0 \leqslant w \leqslant 1000)$
接下来一行输入两个以空格分隔的整数 $s$, $t$。表示阿福当前在 $s$ 城市,准备去往 $t$ 城市。
$(1 \leqslant s, t \leqslant n)$
Output
如果阿福可以从 $s$ 到达 $t$,则输出需要花费的最少时间。否则输出 $-1$。
Sample Input
3 4 1 2 1 2 3 2 1 3 4 1 2 1 1 3
Sample Output
3
Hint
Source
【2016级ACM暑假集训 结训赛(数据结构组)】UMR