TouchStone
  请登录后使用
登录 注册
 系统首页  练习题库  考试列表  判题结果  问题讨论与解答  统计信息与排名
  • 首页
  • 题库
  • P4280
  • 题目
  • P4280A
    限制 : 时间限制 : - MS   空间限制 : 130000 KB
    评测说明 : 1s
    问题描述

    给定一个 N 个点 M 条边的无向图,其中 Bessie 在 1 号点,Elsie 在 2 号点,它们的目的地为 N 号点。Bessie 每经过一条边需要消耗 B 点能量,Elsie 每经过一条边需要消耗 E 点能量。当它们相遇时,它们可以一起行走,此时它们每经过一条边需要消耗 P 点能量。求它们两个到N 号点时最少消耗多少能量?

    输入格式

    第一行 B, E, P, N,M(所有数<=40000,n>=3)

    下面 m 行每行两个数 u,v 表示一条无向边(u,v)。(1<=u,v<=n)

    输出格式

    最小费用。

    样例输入

    4 4 5 8 8
    1 4
    2 3
    3 4
    4 7
    2 5
    5 6
    6 8
    7 8

    样例输出

    22

    提示

    部分分

     

    编号

    N

    M

    1

    8

    8

    2

    492

    1157

     

     

     

    3

    2571

    3206

     

     

     

    4

    3083

    4888

     

     

     

    5

    5292

    5920

    6

    17754

    17838

    7

    11364

    12335

    8

    27086

    28393

     

     

     

    9

    18923

    19215

     

     

     

    10

    36986

    37085

     

     

     

     


    来源  usaco