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。(3N≤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