← 返回题目

题库练习最短距离及花费

← 上一题下一题 →

A71191 | $最短距离及花费$

来源编程题

时间限制1s

内存限制128MB

通过 / 提交0/0

题目描述

A国有 n 个城市，修建了 m 条道路（道路双向都可以走），每条道路的长度为 d ，走该路线要花费 p 元的过路费。 请问：如果要从编号为 s 的城市到编号为 t 的城市，最短距离是多少，如果按最短距离来走要花多少钱？ 注意：如果有多条最短路，请输出花费最少的距离及花费。

输入格式

读入若干组数据，对于每组数据： 先输入 n,m ，城市的编号是 1 \sim n，然后是 m 行，每行 4 个数 a,b,d,p ，表示 a 城市和 b 城市之间有一条边，且其长度为 d ，过路费花费为 p 。 最后一行是两个数 s,t ，表示起点编号为 s ，终点编号为 t 。 当读入 n 和 m为 0 时，表示输入结束。 ( 1 \lt n \le 1000, 0 \lt m \lt 100000， s \neq t )

输出格式

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

输入输出样例

输入 #1

输出 #1

9 11

C++ 编辑器

输入

输出