WA 56pts #5-#7 有没有大佬帮忙看一下qwq 已经卡了两个半小时了
查看原帖
WA 56pts #5-#7 有没有大佬帮忙看一下qwq 已经卡了两个半小时了
774985
rentianxiang楼主2024/5/18 22:49

思路:

  1. 先dfs求出被感染的边
  2. 再用堆优化dijkstra求最短路 代码:
#include<bits/stdc++.h>
using namespace std;
#define int long long
const int N = 400010;
const int inf = 1e18;
using P = pair<int, int>;
int n, m, k, s, p, Q, c[N], vc[N], vs[N], dis[N], f[N];
vector<P> G[N];
priority_queue<P, vector<P>, greater<P> > q;
void dfs(int x, int dep) {
	if (dep == s) {
		return ;
	}
	for (int i = 0; i < G[x].size(); i++) {
		int y = G[x][i].first;
		if (vc[y] == 0 && y != 1 && y != n) {
			vc[y] = 1;
			dfs(y, dep + 1);
		}
	}
}
void dijkstra() {
	for (int i = 1; i <= n; i++)	dis[i] = inf;
	q.push({dis[1] = 0, 1});
	while (!q.empty()) {
		int x = q.top().second;
		q.pop();
		if (vs[x])	continue;
		vs[x] = true;
		for (int i = 0; i < G[x].size(); i++) {
			int y = G[x][i].first;
			if (!vs[y] && dis[y] > dis[x] + f[y]) {
				q.push({dis[y] = dis[x] + f[y], y});
			}
		}
	}
	cout << dis[n] << '\n';
}
signed main() {
	ios::sync_with_stdio(false);
	cin.tie();	cout.tie();
	cin >> n >> m >> k >> s >> p >> Q;
	for (int i = 1; i <= k; i++) {
		cin >> c[i];
		vc[c[i]] = 2;
	}
	for (int i = 1; i <= m; i++) {
		int a, b;
		cin >> a >> b;
		G[a].push_back({b, 0});
		G[b].push_back({a, 0});
	}
	for (int i = 1; i <= k; i++) {
		dfs(c[i], 0);
	}
	for (int i = 2; i < n; i++) {
		if (vc[i] == 0)	f[i] = p;
		if (vc[i] == 1)	f[i] = Q;
		if (vc[i] == 2)	f[i] = inf;
	}
	dijkstra();
	return 0;
}
2024/5/18 22:49
加载中...