题解 P5764 【[CQOI2005]新年好】

· · 题解

让我来仔细梳理一下题目大意，以便大家更好的编写代码。

简化一下题意，就是佳佳要依次拜访五个亲戚，给出一张图及所有人的位置，求最短距离。

首先看，n\leq50000，说明搜索在这题是行不通的。

要我们求最短距离，那就来考虑一下最短路。

由于她是依次不间断拜访，即到达一家后立即前往下一家，所以我们首先可以以这6个点为起点依次跑最短路，得到以这6个点为起点的最短路径。换句话说，我们知道了每两个地方间的最短距离。

接着需要定的，就是拜访顺序了。

由于只有六处，且出发点已经固定，我们就可以考虑枚举全排列，将所有的可能的拜访顺序求出，同时将每个顺序的时间求出，去所有中的最小值即可。

大体思路并不难想，也就是这样，下面让我来分析一下代码细节：

$2.$此题更新数据后卡`SPFA`，所以只能采用`堆优化dijkstra`。 $3.$由于需要求解六处的最短路径，所以存最短路径时用一般的一维数组是肯定不行的。所以我们考虑使用二维数组，其中第一维可以存储出发的亲戚家的编号，第二维跟平时定义一样。 $4.$由于求最小值，所以枚举全排列时可以剪枝：当前用时已经大于过去最小值时，就可以`return`。 总体就是这样。 最后分析一下时间复杂度：枚举全排列时间不大，主要在计算最短路上。采用`堆优化dijkstra`后，耗时为：$O(m\log n)$（常数忽略不计） $AC$ $Code 
#include <iostream>
#include <vector>
#include <queue>
#include <cstring>
#define _for(i, a, b) for (int i=(a); i<=(b); i++)
#define _rep(i, a, b) for (int i=(a); i<(b); i++)
using namespace std;

typedef pair<int, int> P;
const int MAXN = 50010, INF = 1e9;

struct edge {
    int to, cost;
};
std::vector<edge> G[MAXN];
void addedge(int u, int v, int c) {
    G[u].push_back((edge){v, c});
    G[v].push_back((edge){u, c});
}//建无向边操作

int n, m, rel[7], d[7][MAXN], ans = INF;//记得ans要赋INF，以及d数组要开二维
bool vis[7];

void dijkstra(int s) {
    priority_queue<P, vector<P>, greater<P> > q;
    d[s][rel[s]] = 0;
    q.push(P(0, rel[s]));
    while (!q.empty()) {
        P p = q.top();
        q.pop();
        int v = p.second;
        if (p.first > d[s][v]) continue;
        _rep (i, 0, G[v].size()) {
            edge e = G[v][i];
            if (d[s][e.to] > d[s][v]+e.cost) {
                d[s][e.to] = d[s][v]+e.cost;
                q.push(P(d[s][e.to], e.to));
            }
        }
    }
}//标准堆优化dijkstra

void dfs(int cur, int cost, int pos) {
    if (cost > ans) return ;
    if (cur == 5) {
        ans = min(ans, cost);
        return ;
    }
    _for (i, 1, 5) 
        if (!vis[i]) {
            vis[i] = true;
            dfs(cur+1, cost+d[pos][rel[i]], i);
            vis[i] = false;
        }
}//标准枚举全排列

int main() {
    cin >> n >> m;
    _for (i, 1, 5) cin >> rel[i];
    _for (i, 1, m) {
        int u, v, c;
        cin >> u >> v >> c;
        addedge(u, v, c);
    }//建图
    rel[6] = 1;
    memset(d, 0x3f, sizeof(d));//记得d数组要初始化
    _for (i, 1, 6) dijkstra(i);
    dfs(0, 0, 6);
    cout << ans << endl;
    return 0;//完结撒花
}