TouchStone
  请登录后使用
登录 注册
 系统首页  练习题库  考试列表  判题结果  问题讨论与解答  统计信息与排名
  • 首页
  • 题库
  • P3501
  • 题目
  • P3501【2015多校联训6】益智游戏
    限制 : 时间限制 : 10000 MS   空间限制 : 165536 KB
    评测说明 : 1s
    问题描述

    小 P 和小 R 在玩一款益智游戏。游戏在一个正权有向图上进行。 小 P 控制的角色要从 A 点走最短路到 B 点,小 R 控制的角色要从 C 点走最短路到 D 点。 一个玩家每回合可以有两种选择,移动到一个相邻节点或者休息一回合。 假如在某一时刻,小 P 和小 R 在相同的节点上,那么可以得到一次特殊奖励,但是在每 个节点上最多只能得到一次。 求最多能获得多少次特殊奖励。 

    输入格式

    第一行两个整数 n,m 表示有向图的点数和边数。 接下来 m 行每行三个整数 xi,yi,li,表示从 xi到 yi有一条长度为 li的边。 最后一行四个整数 A,B,C,D,描述小 P 的起终点,小 R 的起终点。

    输出格式

    输出一个整数表示最多能获得多少次特殊奖励。若小 P 不能到达 B 点或者小 R 不能到达 D 点则输出-1。

    样例输入

    5 5 
    1 2 1 
    2 3 2 
    3 4 4 
    5 2 3 
    5 3 5 
    1 3 5 4

    样例输出


    2

    提示

    【数据规模】
    对于 30%的数据,满足 n≤50
    对于 60%的数据,满足 n≤1000,m≤5000 对于
    100%的数据,满足 n≤50000,m≤200000,1≤li≤500000000


    来源  bs