[Acwing] (图论最短路+dfs)) 1135. 新年好

https://www.acwing.com/problem/content/1137/

分析问题:

多终点,顺序不同的最短路总和最小值

疑惑:

那么我之前学的那些最短路都是干嘛的？

解答:

之前的最短路是求两个点之间的最短距离或者花费 这个题目要求的是最短距离总和

疑惑:

那么用最小生成树行不行？ prim(O n^2) ,krusal(O mlogn)

解答:

时间复杂度不行,em 你说krusal ? 那不是跑稀疏图 吗

思路办法:

我们先预处理出 6个点到其他点的最短路 然后再通过查表的方式跑dfs 那么时间复杂度就是6*(mlogn) + 5! (因为spfa被卡了 所以用dij 堆优化)

code:

先预处理以每个点为起点的最短距离

for (int i = 0; i  dist[ver] + w[i])
            {
                dist[j] = dist[ver] + w[i];
                heap.push({dist[j], j});
            }
        }
    }
}

然后再跑dfs

printf("%d\n", dfs(1, 0, 0));
   
int dfs(int u, int start, int distance)
{
    if (u > 5)
        return distance;

    int res = INF;
    for (int i = 1; i