56pts WA on#5~#7 大佬们走过路过可以都看看嘛?qwq
查看原帖
56pts WA on#5~#7 大佬们走过路过可以都看看嘛?qwq
1088499
xyd01032wh楼主2024/4/28 19:38

应该没错的思路:

1.先建用链式前向星存一张不带边权的图,用来bfs求被感染的城市。补充一下:1表示有危险的,0表示安全的,-1表示沦陷的。

2.再建一张带边权的图,边权计算的话得继续分类讨论

情况1:起点或终点中有一个为已经沦陷的城市就不建这条边

情况2:如果该边连接n节点,则只建u->v且边权为0的边

情况3:终点城市已经有危险,则建u->v且边权为Q,如果没危险就边权为P(起点同理)

#include <bits/stdc++.h>
using namespace std;
const int N = 5e5 + 5;
int n, m, k, s, c[N], P, Q;

int nxtj[N << 2], headj[N << 2], toj[N << 2], cnttj;
inline void addj(int u, int v)
{
	nxtj[++cnttj] = headj[u];
	headj[u] = cnttj;
	toj[cnttj] = v;
}
struct nodew
{
	int u;
	int step;
};
queue<nodew> qj;
int safe[N];
int xx[N << 2], yy[N << 2];
bool visi[N];
void bfs(int ss)
{
	qj.push({ss, 0});
	while (!qj.empty())
	{
		int u = qj.front().u, ste = qj.front().step;
		qj.pop();
		// if ( u == n)
		// 	continue;
		if (ste == s)
			continue;
		for (int i = headj[u]; i; i = nxtj[i])
		{
			int v = toj[i];
			if (visi[v])
				continue;
			visi[v] = true;
			safe[v] = 1;
			qj.push({v, ste + 1});
		}
	}
}

struct node
{
	int u;
	long long dis;
	bool operator<(const node &a) const
	{
		return dis > a.dis;
	}
};
int nxt[N << 2], head[N << 2], to[N << 2], va[N << 2], cntt;
inline void add(int u, int v, int val)
{
	nxt[++cntt] = head[u];
	head[u] = cntt;
	to[cntt] = v;
	va[cntt] = val;
}
long long dis[N];
bool vis[N];
priority_queue<node> q;
void dijkstra()
{
	q.push({1, 0});
	while (!q.empty())
	{
		int u = q.top().u;
		q.pop();
		if (vis[u])
			continue;
		vis[u] = true;
		for (int i = head[u]; i; i = nxt[i])
		{
			int v = to[i], vanow = va[i];
			if (dis[v] > dis[u] + vanow * 1ll)
			{
				dis[v] = dis[u] + vanow * 1ll;
				q.push({v, dis[v]});
			}
		}
	}
}

int main()
{
	// ios::sync_with_stdio(0);
	// cin.tie(0), cout.tie(0);

	memset(dis,0x3f, sizeof dis);
	cin >> n >> m >> k >> s;
	cin >> P >> Q;
	for (int i = 1; i <= k; i++)
		cin >> c[i];
	for (int i = 1; i <= m; i++)
	{
		cin >> xx[i] >> yy[i];
		addj(xx[i], yy[i]);
		addj(yy[i], xx[i]);
		if (xx[i] > yy[i])
			swap(xx[i], yy[i]);
	}
	for (int i = 1; i <= k; i++)
	{
		visi[c[i]] = true;
		safe[c[i]] = -1;
		bfs(c[i]);
	}
	for (int i = 1; i <= m; i++)
	{
		if (safe[yy[i]] == -1 || safe[xx[i]] == -1)
			continue;
		if (yy[i] == n)
			add(xx[i], yy[i], 0);
		if (safe[yy[i]] == 1)
			add(xx[i], yy[i], Q);
		else if (safe[yy[i]] == 0)
			add(xx[i], yy[i], P);
		if (safe[xx[i]] == 1)
			add(yy[i], xx[i], Q);
		else if (safe[xx[i]] == 0)
			add(yy[i], xx[i], P);
	}
	dis[1] = 0;
	dijkstra();
	cout << dis[n];
	return 0;
}
2024/4/28 19:38
加载中...