New Online Judge 主页 问题 来源/分类 竞赛&作业 状态 排名 常见问答
登录 注册

1772: [NewOJ Contest 8] 回家

内存限制：256 MB 时间限制：1 S 标准输入输出
题目类型：传统 评测方式：文本比较 上传者：
提交：7 通过：3
提交提交记录统计

题目描述

现在有一张地图包含N个点，M条无向边。
小蓝和小红分别在点1和点2，他们需要回家，家在点N。
小蓝单独走某条路的体力消耗是x，小红单独走某条路的体力消耗是y，小蓝小红一起走某条路的体力消耗是z。
z和x+y没有关系，可能单独走体力消耗更小，也可能一起走体力消耗更小。
求最小的体力消耗。

输入格式

输入第一行包含5个正整数，分别表示x,y,z,N,M。（3≤N≤40000,M≤50000）
接下来M行，每行包含u和v，表示存在一条u到v的双向边
数据保证可以从1、2到N。

输出格式

输出一个数字表示答案。

输入样例 复制 

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

输出样例 复制 

22