返回信息流E 旅游公司的难题Accept:0 Submit:0
Time Limit:1000MS Memory Limit:65536KB
Description
我们国家有好多风景优美的城镇，旅游公司推出的黄金周旅游也很受大众的欢迎。
现在旅游公司遇到一件麻烦的事情，因为越来越多的顾客希望走最短路到达他们想去的城镇旅游，而旅游公司又没有开设这项业务。为了抓住市场需求，旅游公司的老总徐先生决定开发一套计算机系统，该系统能够回答顾客的需求。
有的城镇之间可以直接到达，因为他们之间有航线，航线有一定的距离L。但有些城镇之间没有直接相连的航线，只能经过其他的城镇进行周转。
现在，旅欧公司徐先生告诉你所有航线的距离以及该航线的起始城镇和终止城镇，请你写段程序来回答所有的顾客的提问。
Input
输入第一行为两个整数N和M，（0< N < 50，0 < M < 3000），分别表示城镇的数目和航线的数目。接着M行每行三个整数a，b，L（0 < L < 100，a!=b），表示该航线的两个端点是a和b，长度为L。航线有两个方向，即既可以从a到b，也可以从b到a。
M行之后，有一个整数K（0 < K < 100000），表示顾客询问的次数。接着K行，每行两个整数a，b(a!=b)，表示顾客需要从城镇a到城镇b。
城镇的编号从0到N-1。
Output
输出包含K行，每行一个整数，分别表示对应的询问的结果，即两个城镇之间的最短路。如果顾客查询的两个城镇无论怎样中转，都不能到达，你需要输出999999999
Sample Input
6 5
0 1 2
0 2 3
2 3 1
1 3 6
4 5 2
2
0 3
0 5
Sample Output
4
999999999
Hint
注意m和n的关系，可能有重边。
这是一条镜像帖。来源：北邮人论坛 / cpp / #48446同步于 2010/12/28
该镜像源已超过 30 天没有更新，可能在源站已被删除。
CPP机器人发帖
【离散编程作业】有人会做这道题吗，离提交还有半小时，我快哭
liushichuan
2010/12/28镜像同步4 回复
订阅后，新回复会通过你的通知中心匿名送达。
4 条回复
是不是先得到两点之间最短直接距离的矩阵O(M)，然后用floyd算法算出两点间的最短距离O(N^3)。最后查询只要O（1）的时间就可以直接获得了？