九度Online Judge

OJ新增积分机制,如有任何问题或者建议,请发帖到九度论坛OJ意见反馈版,祝大家一切顺利!
亲,九度OJ官方微博开通了,欢迎你来粉!微博地址:weibo.com/jobdu

 题目1406-九度Online Judge,用代码记录你的成长之路!

题目1406:上班啦

时间限制:1 秒

内存限制:32 兆

特殊判题:

提交:544

解决:92

题目描述:

淘小宝最近进入了杭州淘宝实习了,可是他所住的地方离工作地点很远(为了省钱)。虽说杭州是个美丽的旅游城市,可是其公共交通却十分被人诟病,早高峰的时间,汽车跟爬的一样,所以经过一个星期的折腾之后,淘小宝决定骑车前往公司上班。

         为了每天尽可能的节约体力,同时更多地领略杭州城市的美丽风光,淘小宝就想请你告诉他,从他的住所出发,最短的骑车距离是多少?同时,也请你告诉他,在骑车路径最短的前提下,他有多少种不同的选择?

         我们已知淘小宝将整个城市交通按照各个路口以及路口间的道路,抽象成一幅由N 个点与M 条边组成的地图,同时也告知你这些边之间距离,请你告诉淘小宝,最短的骑车距离是多少以及这样长度的不同路径条数。若路径不存在,则按样例输出一行两个-1。

输入:

每个测试案例包含两部分。

第一行输入包括两个整数N和M , 其中N代表地图上不同的路口数量,且2 <= N <= 500。M为总的路径条数,我们保证输入数据中,任意两个点之间的路径不会超过一条,且M一定是非负整数。

第二行开始会输出M行,每行3个正整数,由空格隔开。分别表示这条路径的两个端点E1 和E2,以及这条路径的长度L,其中1 <= L <= 10000。

这里需要注意的是,地图上所有路口是从1开始编号的,其中淘小宝的住处一定被编为1号,而淘宝公司则被编为N号。

输出:

对于每个测试案例,输出一行,每行包含两个整数,用空格分开。若答案存在,则输出最短路径的长度以及方案数;若不存在,则输出-1 -1。

样例输入:
4 4
1 2 1
4 2 1
1 3 1
3 4 1
3 1
1 2 1
样例输出:
2 2
-1 -1