自动搬运

查看原文

来自洛谷，原作者为

	Ak_hjc_using 帅就一个字，我只说一次

搬运于2025-08-24 21:45:16，当前版本为作者最后更新于2024-12-16 18:12:56，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

本题：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;
}