虽然这道题我并没有想到题解中的一维状态并利用最短路就能搞定的dp做法，但我想到了一种差劲一些并且好像很有道理的做法。由于本蒟蒻一直不太会证明dp的合理性以及我的想法可能比较低效+费空间，所以提交之后全部MLE和TLE。再加上这个题自动生成数据容易导致无解，所以目前除了知道能通过样例之外，我完全不知道自己的这个想法是否正确。在这里想请教一下大佬们，看看我的算法是不是正确的。

我的思路是：先是用dfs预处理出所有的能从起点到终点的路径，每找到一条，就状压（根据这条路径经过了哪些点来压缩，如果不考虑起点和终点就是$2^{18}$种可能），标记这条路径可走且记录路径长度。然后，设$f[i][j]$为前i天运输过程中，且第i天走的是状态压缩后结果为j的那条路径，然后考虑从第i-1天到第i天进行转移。转移思路是，如果第i-1天选的路d和第i天选的路j相等，则$f[i][j]=min\{f[i][j],f[i-1][d]+length[j]\}$，即只是加这条路的长度，否则的话，$f[i][j]=min\{f[i-1][d]+length[d]+k\}$（或许可以滚动数组优化空间，但我暂时还没用），即加这条路的长度和切换路线的开销。在不考虑更细节的东西的情况下，请问大佬们这道题这样想是否是对的？谢谢！