有序的最短路径问题，具体问题如下

TSwangming

小明在一家网络科技服务公司工作，公司在n个城市有网络安全技术巡检维护服务业务，小明所在的公司位于其中的一个城市，公司根据业务需要，计划派小明到其中m城市分别去为客户做相应的服务工作。小明计划每完成一个城市客户的服务工作后，直接从该城市去往下一个城市，完成公司指派的所有城市的服务工作后，返回公司所在城市。出发前小明按照客户服务约定顺序，列出了前往各城市的次序，按照公司规定的出差旅途费用按照每公里1元计算，公司希望小明提交一个最少的差旅费用清单。请你设计一个算法并编写程序帮助小明列出到每一个计划前去的城市的费用及总费用清单，并通过程序验证该方案的正确性，分析算法的时间复杂度。

傻眼貓咪

（一）假设题目有例子最好，比如；输入 xxx 输出 yyy，这样一来，大家都清楚知道你的题目细节，以及答案的输出的格式。
（二）题目很多不完整地方，比如完成所有城市服务后，直接返回公司（忽略路程），还是沿着原本的城市的路返回公司，还是有其它路？或是更多路线，像网格一样？
（三）比如 A 城市可以去 B 城市也可以去 C 城市，C 城市可以直接去 B 城市吗？（需要经过 A 城市吗？）

TSwangming

傻眼貓咪 发表于 2022-5-20 22:35
（一）假设题目有例子最好，比如；输入 xxx 输出 yyy，这样一来，大家都 ...

完成任务后，从最后一个城市返回原公司，中间可以路过其他城市，只要保证所有需要到的城市按顺序走完，路程最短就行

TSwangming

傻眼貓咪 发表于 2022-5-20 22:35
（一）假设题目有例子最好，比如；输入 xxx 输出 yyy，这样一来，大家都 ...

假设顺序是ACDF，那么从A到C也可以经过其他城市

傻眼貓咪

TSwangming 发表于 2022-5-20 22:57
完成任务后，从最后一个城市返回原公司，中间可以路过其他城市，只要保证所有需要到的城市按顺序走完，路 ...

那么中间路过的这些城市费用不就变成 2 倍？（因为来回两次）

TSwangming

傻眼貓咪 发表于 2022-5-20 23:03
那么中间路过的这些城市费用不就变成 2 倍？（因为来回两次）

应该是考虑到顺序问题，虽然经过了那个城市，但是顺序没到，到了也没有用

傻眼貓咪

TSwangming 发表于 2022-5-20 23:08
应该是考虑到顺序问题，虽然经过了那个城市，但是顺序没到，到了也没有用

戴克斯特拉演算法（Dijkstra's algorithm）

TSwangming

傻眼貓咪 发表于 2022-5-20 23:09
戴克斯特拉演算法（Dijkstra's algorithm）

可是这样能保证是按顺序的吗

傻眼貓咪

TSwangming 发表于 2022-5-20 23:36
可是这样能保证是按顺序的吗

你可以试试忽略不符合顺序的路线，只选顺序路线便可。