算法提高课汇总

模型抽象

• $n$个车站, $m$条双向公路: $n$个顶点, $m$条边的无向图.

• 佳佳的家在车站$1$, 需要摆放5个亲戚: 起点$s = 1$, 求经过$5$个顶点的最短距离.

$dfs$ + $dijkstra$

因为摆放$5$个亲戚的顺序任意, 可以考虑用$dfs$枚举摆放顺序, 计算相邻顶点的最短路径.
如摆放顺序$a, b, d, c, e$, 则我们利用$djikstra$计算$s$-->$a$、$a$-->$b$, $…$,$c$-->$e$最短路径.
求所有摆放顺序中最短路径和的最小值即可.

考虑时间复杂度: $dfs$时间复杂度为$5!$, 且每次需要通过$dijkstra$计算$5$对起点到终点的
最短路径, 时间复杂度为$5!\times 5m\lg(n) \approx 8\times 10^8$, 超时.

这里可以使用预处理以降低时间复杂度的方法, 即改变我们计算的顺序.

$dijkstra$ + $dfs$

首先通过$dijkstra$计算以$s, a, b, c, d, e$中任意一点为源点到其他点的最短路径, 存储在哈希表中.
再通过$dfs$枚举所有摆放顺序, 每次相邻点对的距离通过查表即可得到. 时间复杂度为$6\times m\lg(n)+5!$.

代码实现

#include <queue>
#include <cstring>
#include <iostream>

#define w first
#define u second

using namespace std;

typedef pair<int, int> pii;

const int N = 50010, M = 2e5 + 10, INF = 0x3f3f3f3f;

int n, m;
int source[6]; //起点以及5个亲戚的车站编号
int h[N], e[M], w[M], ne[M], idx; 
int dist[N], g[6][6]; // g[i][j]: source[i]->source[j]的最短路径 
bool st[N];

void add(int u, int v, int c)
{
    e[idx] = v, w[idx] = c, ne[idx] = h[u], h[u] = idx ++;
}

//以source[index]为起点计算单源最短路 并更新g[index][j]
void dijstra(int index)
{
    memset(st, 0, sizeof st);
    memset(dist, 0x3f, sizeof dist); //一行

    int s = source[index]; 
    dist[s] = 0;
    priority_queue<pii, vector<pii>, greater<pii>> pque;
    pque.push({dist[s], s});

    while( pque.size() )
    {
        while( pque.size() && st[pque.top().u] )   pque.pop();
        if( pque.empty() )  break;

        int u = pque.top().u;
        st[u] = true;

        for( int i = h[u]; ~i; i = ne[i] )
        {
            int v = e[i];
            if( dist[v] > dist[u] + w[i] )
            {
                dist[v] = dist[u] + w[i];
                pque.push({dist[v], v});
            }
        }
    }

    for( int i = 0; i < 6; i ++ )   g[index][i] = dist[source[i]];
}

//dfs u:枚举次数; index: 当前位置source[index]; distance: 到达当前点经过的距离
int dfs(int u, int index, int distance)
{//u = 0时枚举第1个顶点 u = 4时枚举第5个顶点 u = 5时枚举完毕
    if( u == 5 )    return distance; //遍历完毕

    int res = INF; //从当前起点ver出发摆放剩余节点的最小距离
    for( int i = 1; i <= 5; i ++ )
    {
        if( !st[i] )
        {
            st[i] = true;
            res = min( res, dfs(u + 1, i, distance + g[index][i]) );
            st[i] = false;
        }
    }
    return res;
}

int main()
{
    cin >> n >> m;
    source[0] = 1; //起点
    for( int i = 1; i <= 5; i ++ )  cin >> source[i];

    memset(h, -1, sizeof h);
    while( m -- )
    {
        int a, b, c;
        cin >> a >> b >> c;
        add(a, b, c), add(b, a, c);
    }

    for( int i = 0; i < 6; i ++ )   dijstra(i);

    memset(st, false, sizeof st);
    cout << dfs(0, 0, 0) << endl;

    return 0;
}