P1951 收费站_NOI导刊2009提高(2)

    • 610通过
    • 3.6K提交
  • 题目提供者
  • 评测方式 云端评测
  • 标签 图论 快速排序,快排 最短路 模拟 NOI导刊 高性能
  • 难度 提高+/省选-
  • 时空限制 1000ms / 128MB

题解

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

    推荐的相关题目 显示

    题目描述

    在某个遥远的国家里,有n个城市。编号为1,2,3,…,n。

    这个国家的政府修建了m条双向的公路。每条公路连接着两个城市。沿着某条公路,开车从一个城市到另一个城市,需要花费一定的汽油。

    开车每经过一个城市,都会被收取一定的费用(包括起点和终点城市)。所有的收费站都在城市中,在城市间的公路上没有任何的收费站。

    小红现在要开车从城市u到城市v(1<=u,v<=n)。她的车最多可以装下s升的汽油。在出发的时候,车的油箱是满的,并且她在路上不想加油。

    在路上,每经过一个城市,她都要交一定的费用。如果某次交的费用比较多,她的心情就会变得很糟。所以她想知道,在她能到达目的地的前提下,她交的费用中最多的一次最少是多少。这个问题对于她来说太难了,于是她找到了聪明的你,你能帮帮她吗?

    输入输出格式

    输入格式:

    第一行5个正整数,n,m,u,v,s,分别表示有n个城市,m条公路,从城市u到城市v,车的油箱的容量为s升。

    接下来的有n行,每行1个整数,fi表示经过城市i,需要交费fi元。

    再接下来有m行,每行3个正整数,ai,bi,ci(1<=ai,bi<=n),表示城市ai和城市bi之间有一条公路,如果从城市ai到城市bi,或者从城市bi到城市ai,需要ci升的汽油。

    输出格式:

    仅一个整数,表示小红交费最多的一次的最小值。

    如果她无法到达城市v,输出-1.

    输入输出样例

    输入样例#1: 复制
    4 4 2 3 8
    8
    5
    6
    10
    2 1 2
    2 4 1
    1 3 4
    3 4 3
    
    输出样例#1: 复制
    8

    说明

    【数据规模】

    对于60%的数据,满足n<=200,m<=10000,s<=200

    对于100%的数据,满足n<=10000,m<=50000,s<=1000000000

    对于100%的数据,满足ci<=1000000000,fi<=1000000000,可能有两条边连接着相同的城市。

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