题解：P3096 [USACO13DEC] Vacation Planning G

· · 题解

本题：P3096 [USACO13DEC] Vacation Planning G\ 弱化版：P3094 [USACO13DEC] Vacation Planning S

思路

其实就是 Dijkstra 的模板题。

题目意思简化为：

给定一张 n 个点，m 条边的无向图，k 个关键点，给定 Q 次询问，每次询问从 s 到 t 必须经过至少一个关键点的最短路径。

思路：

弱化版：由于数据量非常小，n \le 200，故直接 floyd 算出所有点的最短路径，枚举所有中转点（也就是关键点），算出答案即可。

本题：由于数据量比较大，使 floyd 无法通过本题，所有我们可以使用 Dijkstra 算法，时间复杂度稳定 O((n+m) \log m)，可以过本题。

如果是使用 Dijkstra 算法，那么中转点怎么记录呢？，设有一条路径，1 -> 2 -> 3，其中 2 是关键点，那么这条路径就可以化为 1 -> 2 的路径，加上 2 -> 3 的路径，那么就巧妙地转化了中转点的问题，对每一个关键点进行 Dijkstra，记录两个数组，分别用来记录 1 到关键点的距离和关键点到 n 的距离，统计答案时相加即可。

重点（需要优化的地方）

我们不是记录了两个二维数组吗？但是这样的话，由于 n \le 2 \times 10^4，所以导致空间复杂度太高了，超过了内存限制，但是发现这里的 k 非常小，所有我们可以把所有的关键点转换为它们各自的编号，用一个数组记录即可。

代码：

#include <iostream>
#include <vector>
#include <queue>
#define int long long
using namespace std;
const int N = 2e4 + 5, M = 800;
int n, m, k, q, dis_1[M][N], vis[N];
int dis_2[M][N], u[N], v[N], w[N], flag[N], val[N];
const int INF = 1e18;
struct Edge {
    int v;
    int w;
};
struct Node {
    int id, w;
    bool operator < (const Node &a) const {
        return w > a.w;
    }
};
vector<Edge> G[N];
void add_edge(int u, int v, int w) {
    G[u].push_back({v, w});
    return ;
}
void Dijkstra(int *dis, int s) {   
    for (int i = 1; i <= n; i++) {
        dis[i] = INF;
        vis[i] = 0;
    }
    priority_queue<Node> Q;
    Q.push({s, 0});
    dis[s] = 0;
    while (!Q.empty()) {
        Node u = Q.top();
        Q.pop();
        if (vis[u.id] == true) continue ;
        vis[u.id] = true;
        for (int i = 0; i < G[u.id].size(); i++) {
            int v = G[u.id][i].v, w = G[u.id][i].w;
            if (vis[v] == false && dis[v] > dis[u.id] + w) {
                dis[v] = dis[u.id] + w;
                Q.push({v, dis[v]});
            }
        }
    }
    return ;
}
signed main()  {
    ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
    cin >> n >> m >> k >> q;
    for (int i = 1; i <= m; i++) cin >> u[i] >> v[i] >> w[i];
    for (int i = 1; i <= k; i++) {
        cin >> val[i];
        flag[val[i]] = i;
    }
    for (int i = 1; i <= m; i++) add_edge(u[i], v[i], w[i]);
    for (int i = 1; i <= k; i++) Dijkstra(dis_1[i], val[i]);
    for (int i = 1; i <= n; i++) G[i].clear();
    for (int i = 1; i <= m; i++) add_edge(v[i], u[i], w[i]);
    for (int i = 1; i <= k; i++) Dijkstra(dis_2[i], val[i]);
    for (int i = 1; i <= n; i++) G[i].clear();
    int cnt = 0, sum = 0;
    while (q --) {
        int s, t;
        cin >> s >> t;
        int ans = 1e18;
        if (flag[s]) ans = dis_1[flag[s]][t];
        if (flag[t]) ans = min(ans, dis_2[flag[t]][s]);
        if (ans == 1e18) {
            for (int i = 1; i <= k; i++) ans = min(ans, dis_1[i][t] + dis_2[i][s]);
        }
        if (ans != 1e18) {
            cnt ++;
            sum += ans;
        }
    }
    cout << cnt << '\n' << sum << endl;
    return 0;
}