TSP
所属分类:数据结构
开发工具:C/C++
文件大小:554KB
下载次数:37
上传日期:2018-12-24 15:16:27
上 传 者:
哈哈哈叶大傻
说明: Traveling Salesman Problem
市场上有很多种商品,旅行商 Shrek 做短期买卖赚取差价。他从一个城市购买一件商品,到达下一个相邻的城市就卖掉。如果这一次买卖无利可图,那么他就不会这么走。凭着自己和同伴多年的经验,他已经对地图上 n 个城市之间的差价了如指掌。两城市间可能有多种商品可赚取差价,此时 Shrek 只好倒卖利润最大的一件商品。
现在请你帮 Shrek 规划一条路线,使他能赚最多的钱。
输入
第一行两个整数 n、m。表示有 n 个城市,编号 1 ~ n
接下来有 m 行,每行三个整数 a、b、price,表示从城市 a 到城市 b 可赚取差价 price。
输出
若干空格分隔的整数,连成一条赚钱最多的路线。若有多条,输出字典序最小的那条路线(编号小的城市靠前的路线优先输出)
输入样例
4 4
2 1 5
1 3 3
3 4 1
1 4 5
输出样例
2 1 4
(Traveling Salesman Problem)
文件列表:
TSP (0, 2018-12-24)
TSP\TSP.cpp (11035, 2018-12-04)
TSP\TSP.o (161863, 2018-12-04)
TSP\项目1.dev (897, 2018-12-04)
TSP\项目1.exe (2122935, 2018-12-04)
TSP\项目1.layout (97, 2018-12-04)
近期下载者:
相关文件:
收藏者: