程序设计在线测试 主页 问题 来源/分类 考试&作业 状态 排名 班级 常见问答
登录

1555: 两个顶点之间的最短路径

内存限制：128 MB 时间限制：1.000 S
评测方式：文本比较 命题人：
提交：3 解决：3
提交提交记录统计讨论版露一手!

题目描述

若两个顶点之间存在多条路径，则其中必有一条路径长度最短的路径。求两个顶点之间的最短路径。

输入

输入有多个无向图的情况。每种情况先输入一行正整数m、n，分别表示有m个顶点、n条边。顶点序号从1开始。接着有n行，每行2个正整数表示顶点之间有边。接着输入整数r，表示r对顶点，接着输入r行，每行表示顶点p顶点q。

输出

求出各对顶点之间的最短路径。

样例输入 复制 

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

样例输出 复制 

3145

来源/分类