P1685 游览

    • 49通过
    • 120提交
  • 题目提供者 yeszy 管理员
  • 评测方式 云端评测
  • 标签 图论 高性能
  • 难度 省选/NOI-
  • 时空限制 1000ms / 128MB

题解

  • 提示:收藏到任务计划后,可在首页查看。
  • 最新讨论 显示

    推荐的相关题目 显示

    题目描述

    顺利通过了黄药师的考验,下面就可以尽情游览桃花岛了!

    你要从桃花岛的西头开始一直玩到东头,然后在东头的码头离开。可是当你游玩了一次后,发现桃花岛的景色实在是非常的美丽!!!于是你还想乘船从桃花岛东头的码头回到西头,再玩一遍,但是桃花岛有个规矩:你可以游览无数遍,但是每次游玩的路线不能完全一样。

    我们把桃花岛抽象成了一个图,共n个点代表路的相交处,m条边表示路,边是有向的(只能按照边的方向行走),且可能有连接相同两点的边。输入保证这个图没有环,而且从西头到东头至少存在一条路线。两条路线被认为是不同的当且仅当它们所经过的路不完全相同。

    你的任务是:把所有不同的路线游览完一共要花多少时间?

    输入输出格式

    输入格式:

    第1行为5个整数:n、m、s、t、t0,分别表示点数,边数,岛西头的编号,岛东头的编号(编号是从1到n)和你乘船从岛东头到西头一次的时间。

    以下m行,每行3个整数:x、y、t,表示从点x到点y有一条行走耗时为t的路。

    每一行的多个数据之间用一个空格隔开,且:2<=n<=10000; 1<=m<=50000;t<=10000;t0<=10000

    输出格式:

    假设总耗时为total,则输出total mod 10000的值(total对10000取余)。

    输入输出样例

    输入样例#1: 复制
    3 4 1 3 7
    1 2 5
    2 3 7
    2 3 10
    1 3 15
    
    输出样例#1: 复制
    56

    说明

    【样例说明】

    共有3条路径可以从点1到点3,分别是1-2-3,1-2-3,1-3。

    时间计算为:

    (5+7)+7 +(5+10)+7 +(15)=56

    提示
    标程仅供做题后或实在无思路时参考。
    请自觉、自律地使用该功能并请对自己的学习负责。
    如果发现恶意抄袭标程,将按照I类违反进行处理。