社区讨论
为什么只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 条回复,欢迎继续交流。
正在加载回复...