4600: 【最短路问题】2024D-快递员的烦恼
金币值:
1
Time Limit:4.000 s
Memory Limit:128 M
Solved:49
Submit:139
正确率:35.25% Creator:
Description
快递公司每日早晨,给每位快递员推送需要送到客户手中的快递以及路线信息。
快递员自己又查找了一些客户与客户之间的路线距离信息,请你依据这些信息,给快递员提供一条最短路线图,保证使快递员路程的总距离最短。
注意:
1. 不限制快递员送快递到客户手中的顺序,但必须保证最终到客户手中
2. 用例保证一定存在快递员从快递站点送到客户之间的距离,但不保证客户与客户之间的距离。客户位置及快递站均为允许多次经过
3. 所有快递送完后,快递员需回到快递站
Input
首行输入两个正整数 n, m
接下来 n 行,每行输入 2 个整数快递信息,格式为:客户 id 快递送到客户手中的距离 distance
再接下来 m 行,每行输入 3 个整数客户之间的距离信息,格式为:客户 id1 客户 id2 两个客户之间的距离 distance
在行末有换行符。数据保证输入均为以换行符隔开的整数。
Output
最短路径距离,如无法找到则输出 -1
Sample Input Copy
2 1
1 1000
2 1200
1 2 300
Sample Output Copy
2500
HINT
0 < n <= 10
0 < m <= 10
0 <= 客户 id <= 1000
0 < distance <= 10000