43pts WA on #3~#6 求调
查看原帖
43pts WA on #3~#6 求调
794083
Z3k7223ios::sync楼主2023/12/19 13:23

思路为BFS标记危险点+SPFA求最短路,玄关感谢

#include <iostream>
#include <queue>
#include <vector>
#include <cstring>
#include <climits>
using namespace std;
#define ll long long
const int N = 100005;

struct node {
	int x, step;
};

struct edge {
	int to, cost;
};
vector<edge> map[N];
int n, m, k, s, p1, q1;
ll dis[N];
bool dan[N], book[N], cantgo[N], vis[N];
ll cost[N];
queue<node> q;
queue<int> spq;

void bfs() {
	while (!q.empty()) {
		node tmp = q.front();
		q.pop();
		dan[tmp.x] = 1;
		if (tmp.step == k)
			continue;
		for (edge i : map[tmp.x]) {
			if (!book[i.to]) {
				book[i.to] = 1;
				q.push({i.to, tmp.step + 1});
			}
		}
	}
}

void spfa() {
	memset(dis, 0x3f, sizeof(dis));
	spq.push(1);
	vis[1] = 1;
	dis[1] = 0;
	while (!spq.empty()) {
		int u = spq.front();
		spq.pop();
		vis[u] = 0;
		for (int i = 0; i < map[u].size(); i++) {
			int v = map[u][i].to;
			int w = map[u][i].cost;
			if (dis[u] + w < dis[v] && !cantgo[v]) {
				dis[v] = dis[u] + w;
				if (!vis[v]) {
					spq.push(v);
					vis[v] = 1;
				}
			}
		}
	}
}

int main() {
	cin >> n >> m >> k >> s >> p1 >> q1;
	for (int i = 1; i <= k; i++) {
		int u;
		cin >> u;
		q.push({u, 0});
		book[u] = 1;
		cantgo[u] = 1;
	}
	for (int i = 1; i <= m; i++) {
		int u, v;
		cin >> u >> v;
		map[u].push_back({v, 0});
		map[v].push_back({u, 0});
	}
	bfs();
	for (int i = 1; i <= n; i++) {
		if (dan[i]) {
			cost[i] = q1;
		} else {
			if (cantgo[i]) {
				cost[i] = LONG_LONG_MAX - 5e5;
			} else {
				cost[i] = p1;
			}
		}
	}
	//cost[1] = 0, cost[n] = 0;
	for (int i = 1; i <= n; i++) {
		for (int j = 0; j < map[i].size(); j++) {
			map[i][j].cost = (cost[i] + cost[map[i][j].to]);
			//cout << "from " << i << " to " << map[i][j].to << " costs " << map[i][j].cost << endl;
		}
	}
	//cout << dis[15] << endl;
	spfa();
//	for (int i = 1; i <= n; i++) {
//		cout << dis[i] << ' ';
//	}
	//cout << endl;
	cout << (dis[n] - cost[1] - cost[n] >> 1LL) << endl;
	return 0;
}
2023/12/19 13:23
加载中...