最小交通费用问题

成绩 100 开启时间 2016年05月22日 星期日 20:15
折扣 0.8 折扣时间 2016年05月22日 星期日 20:15
允许迟交 是 关闭时间 2016年05月22日 星期日 20:15
输入文件 road.in 输出文件 road.out

【题目描述】最小交通费用问题(road.cpp/c/pas)

魔法世界有N（Ｎ<100）个城市，某些城市之间有公路连接，任意两个城市可以通过公路直接或者间接到达，并且任意有公路连接的两个场所之间，来回使用的交通工具不一样，所以费用也不一样，现从A场所出发去B场所，最后再返回A场所，请设计一条来回最小交通费用的线路。

【输入格式】

　　第一行有两个数N，M（N为场所个数，M为场所间交通路线图）

　　第二行至第M+1行分别有三个数字，前两个为场所编号，第三个为它们的交通费用。

　　第M+2行有两个数字，为两个求解的场所编号。

【输出格式】

　　一个整数（最小交通费）。

【输入样例】

　　3 5

　　1 2 4

　　2 1 6

　　1 3 11

　　3 1 3

　　2 3 2

　　1 2

【输出样例】

　　9