2144: 【入门】最短距离及花费

内存限制:128 MB 时间限制:1.000 S 标准输入输出
题目类型:传统 评测方式:文本比较 上传者:
提交:2 通过:2

题目描述

A国有n个城市,修建了m条道路(道路双向都可以走),每条道路的长度为d,走该路线要花费p元的过路费。

请问:如果要从编号为s的城市到编号为t的城市,最短距离是多少,如果按最短距离来走要花多少钱?

注意:如果有多条最短路,请输出花费最少的距离及花费。

输入格式

读入若干组数据,对于每组数据:

先输入n,m,城市的编号是1~n,然后是m行,每行4个数 a,b,d,p,表示a城市和b城市之间有一条边,且其长度为d,过路费花费为p。

最后一行是两个数 s,t,表示起点编号为s,终点编号为t。

当读入n和m为0时,表示输入结束。
(1<n≤1000, 0<m<100000, s != t)

输出格式

对于每组输入,输出一行有两个数, 表示最短距离及其花费。

输入样例 复制

3 2
1 2 5 6
2 3 4 5
1 3
0 0

输出样例 复制

9 11

分类标签