社区讨论

为什么只AC一个点……???各位大佬帮忙查一下, 谢谢

P3393逃离僵尸岛参与者 1已保存回复 0

讨论操作

快速查看讨论及其快照的属性,并进行相关操作。

当前回复
0 条
当前快照
1 份
快照标识符
@mi7cs44b
此快照首次捕获于
2025/11/20 19:33
4 个月前
此快照最后确认于
2025/11/20 19:33
4 个月前
查看原帖
CPP
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cstring>
#include <vector>
#include <queue>

#define int long long
#define R int
#define INF 2147483647000
const int M = 500500;
struct EDGE{
	int v, w, net;
}e[M << 2];
int head[M << 1], tot, n, m, k, s, P, Q;
bool c[M << 1], vis[M << 1], v[M << 1];
int dis[M << 1];
std::queue<int> q;

inline void read(int &x)
{
	x = 0;
	int f = 1;
	char c = getchar();
	while (!isdigit(c))
	{
		if (c == '-') f = -1;
		c = getchar();
	}
	while (isdigit(c))
	{
		x = x * 10 + (c ^ 48);
		c = getchar();
	}
	x *= f;
}

inline void add(int x, int y)
{
	e[++tot].v = y;
	e[tot].w = 1;
	e[tot].net = head[x];
	head[x] = tot;
}

void SPFA(int start)
{
	memset(vis, 0, sizeof(vis));
	for (int i = 0; i <= n + 50; ++i)
		dis[i] = INF;
	while (!q.empty()) q.pop();
	q.push(start);
	dis[start] = 0;
	vis[start] = 1;
	int x;
	while (!q.empty())
	{
		x = q.front();
		q.pop();
		vis[x] = 0;
		for (R i = head[x]; i; i = e[i].net)
			if (dis[e[i].v] > dis[x] + e[i].w)
			{
				dis[e[i].v] = dis[x] + e[i].w;
				if (!vis[e[i].v])
				{
					vis[e[i].v] = 1;
					q.push(e[i].v);
				}
			}
	}
}

signed main()
{
	int x, y;
	read(n), read(m), read(k), read(s), read(P), read(Q);
	for (R i = 1; i <= k; ++i) read(x), c[x] = 1;
	for (R i = 1; i <= m; ++i)
	{
		std::cin >> x >> y;
		read(x), read(y);
		if (c[x] && c[y]) continue;
		if (c[x]) add(0, y), add(y, 0);
		else if (c[y]) add(0, x), add(x, 0);
		else add(x, y), add(y, x);
	}
	SPFA(0);
	for (R i = 1; i <= n; ++i) if (dis[i] <= s) v[i] = 1;
	for (R i = 1; i <= tot; ++i)
	{
		if (v[e[i].v]) e[i].w = Q;
		else if (c[e[i].v]) e[i].w = INF;
		else e[i].w = P;
		if (e[i].v == 1 || e[i].v == n) e[i].w = 0;
	}
	SPFA(1);
	printf("%lld", dis[n]);
	return 0;
}

回复

0 条回复,欢迎继续交流。

正在加载回复...