42分求教
查看原帖
42分求教
188155
K2sen楼主2020/8/2 09:49
#include <bits/stdc++.h>
#define ll long long
#define N 100010
#define M 1010

using namespace std;
int n, m, k, s, s1, s2, jiang[N], cnt;
int head[N << 2], add_edge, siz[N], vis[N], dis[N], point[N];
struct CCC {
	int next, to;
}edge[N << 2];
struct node {
	int x, dis;
	bool operator < (const node &b) const {
		return dis > b.dis;
	}
};

int read() {
	int s = 0, f = 0; char ch = getchar();
	while (!isdigit(ch)) f |= (ch == '-'), ch = getchar();
	while (isdigit(ch)) s = s * 10 + (ch ^ 48), ch = getchar();
	return f ? -s : s;
}

void add(int from, int to) {
	edge[++add_edge].next = head[from];
	edge[add_edge].to = to;
	head[from] = add_edge;
}

void bfs(int x) {
	queue<int> q; q.push(x); siz[x] = 0;
	while (!q.empty()) {
		int x = q.front(); q.pop();
		for (int i = head[x]; i; i = edge[i].next) {
			int to = edge[i].to;
			siz[to] = siz[x] + 1;
			if (siz[to] <= s) {
				point[to] = s2;
				if (siz[to] < s) q.push(to);
			} else continue;
		}
	}
}

void dijkstra() {
	memset(dis, 0x3f, sizeof dis);
	priority_queue<node> q;
	q.push((node){1, 0}); dis[1] = 0;
	while (!q.empty()) {
		node fr = q.top(); q.pop();
		int x = fr.x;
		if (vis[x]) continue;
		vis[x] = 1;
		for (int i = head[x]; i; i = edge[i].next) {
			int to = edge[i].to;
			if (!vis[to] && dis[to] > dis[x] + point[to]) {
				dis[to] = dis[x] + point[to];
				q.push((node){to, dis[to]});
			}
		}
	}
}

int main() {
	n = read(), m = read(), k = read(), s = read();
	s1 = read(), s2 = read();
	for (int i = 1, x; i <= k; i++) {
		x = read(), vis[x] = 1;
		jiang[++cnt] = x;
	}
	for (int i = 1, x, y; i <= m; i++) {
		x = read(), y = read();
		add(x, y), add(y, x);
	}
	for (int i = 1; i <= cnt; i++)
		bfs(jiang[i]); 
	for (int i = 1; i <= n; i++)
		if (!point[i]) point[i] = s1;
	point[1] = point[n] = 0;
	dijkstra();
	cout << dis[n];
}
2020/8/2 09:49
加载中...