锰锌袜子求条,P3383,WAon#3#5#6#7
  • 板块灌水区
  • 楼主Bismuth_
  • 当前回复1
  • 已保存回复2
  • 发布时间2024/8/21 15:20
  • 上次更新2024/8/21 17:16:53
查看原帖
锰锌袜子求条,P3383,WAon#3#5#6#7
766934
Bismuth_楼主2024/8/21 15:20
#include <bits/stdc++.h>
using namespace std;
#define pii pair<int,int>
#define int long long
const int N = 1e6 + 10;

struct edge {
	int nxt, to, w;
} e[N];
int n, m, k, s, p, q, idx, vis[N], op[N], h[N], U[N], V[N], dist[N], bk[N];

void add(int u, int v, int w) {
	idx++, e[idx] = {h[u], v, w}, h[u] = idx;
}

void bfs(int st) {
	queue<pii>q;
	q.push({st, 0});
	while (!q.empty()) {
		int u = q.front().first, step = q.front().second;
		q.pop();
		if (vis[u] || step > s)
			continue;
		vis[u] = 1;
		if (!op[u])
			op[u] = 1;
		for (int i = h[u]; i != -1; i = e[i].nxt)
			q.push({e[i].to, step + 1});
	}
}

void dijkstra() {
	for (int i = 2; i <= n; i++)
		dist[i] = 1e17;
	priority_queue<pii, vector<pii>, greater<pii>>q;
	q.push({0, 1});
	while (!q.empty()) {
		int u = q.top().second;
		q.pop();
		if (bk[u] || op[u] == -1)
			continue;
		bk[u] = 1;
		for (int i = h[u]; i != -1; i = e[i].nxt) {
			int v = e[i].to, w = e[i].w;
			if (dist[v] > dist[u] + w) {
				dist[v] = dist[u] + w;
				q.push({dist[v], v});
			}
		}
	}
	cout << dist[n] / 2;
}

signed main() {
	cin >> n >> m >> k >> s >> p >> q;
	memset(h, -1, sizeof(h));
	for (int i = 1; i <= k; i++) {
		int x;
		cin >> x;
		op[x] = -1;
	}
	for (int i = 1; i <= m; i++) {
		cin >> U[i] >> V[i];
		add(U[i], V[i], 1);
		add(V[i], U[i], 1);
	}
	for (int i = 1; i <= n; i++)
		if (op[i] == -1)
			bfs(i);
	memset(h, -1, sizeof(h));
	for (int i = 1; i <= m; i++)
		e[i] = {0, 0, 0};
	idx = 0;
	op[1] = op[n] = 2;
	for (int i = 1; i <= m; i++) {
		int w1, w2;
		if (op[U[i]] == -1 || op[V[i] == -1]) {
			add(U[i], V[i], 1), add(V[i], U[i], 1);
			continue;
		}
		if (op[U[i]] == 1)
			w2 = q;
		else if (op[U[i]] == 0)
			w2 = p;
		else
			w2 = 0;
		if (op[V[i]] == 1)
			w1 = q;
		else if (op[V[i]] == 0)
			w1 = p;
		else
			w1 = 0;
		add(U[i], V[i], w1 + w2), add(V[i], U[i], w2 + w1);
	}
	dijkstra();
	/*	for(int i=1;i<=n;i++){
			for (int j = h[i]; j != -1; j= e[i].nxt){
				cout<<e[j].to<<' '<<e[j].w;
			}
		}*/
	return 0;
}
2024/8/21 15:20
加载中...