“给定起始节点和目标节点以及路径上要避开的节点列和必经节点列”这个限制条件来设计程序不要太复杂哦!
追答dijkstra不太好做,至少我不会。
推荐你用spfa,它可以解决这道题。
避开的节点可以直接删掉与它相邻的边。
对于剩余的图,首先我们需要拆点。
对于点i,们拆成i和i'。如果i点是必经点,那么从i向i'连一条边权为-W(W>所有原图边权总和),否则连一条边权为0的边。对于边i->j,变成i'->j。边权不变。
用spfa求出最短路,得到的ans+W*必经点数目就是解。(dijkstra不能求边权为负的最短路)
当然这样做有一种情况做不了,那就是必经点围成一个环。解决方法是用强连通分量缩点。
时间复杂度为O(kE) (spfa复杂度,不比dijkstra差)