卡常最后一个点
查看原帖
卡常最后一个点
1076087
2023111206li楼主2024/7/20 11:17
#include<bits/stdc++.h>
using namespace std;
#define ll  long long
#define Max 200009
#define inf 1000000000000
int n, m, k, s, p, q;
ll dist[Max];
int ganran[Max];
vector<int> e[Max];
bool jiaqian[Max];
bool vis[Max];
void dfs(int root, int grandfa, int juli)
{
	jiaqian[root] = 1;
	if (!(juli-1))
		return;
	for (auto son : e[root])
	{
		if (son == grandfa)
			continue;
		dfs(son, root, juli - 1);
	}
}
void built()
{
	cin >> n >> m >> k >> s >> p >> q;
	for (int i = 1; i <= k; i++)
	{
		cin >> ganran[i];
	}
	for (int i = 1; i <= m; i++)
	{
		ll x, y;
		cin >> x >> y;
		e[x].push_back(y);
		e[y].push_back(x);
	}
	for (int i = 1; i <= k; i++)
	{
		dfs(ganran[i], 0, s +1);
	}
}
struct bian
{
	int from;
	int to;
	ll val;
	friend bool operator <(const bian& q1, const bian& q2)
	{
		return q1.val > q2.val;
	}
};
void dijs()
{
	priority_queue<bian, vector<bian>> qbian;
	for (int i = 1; i <= n; i++)
		dist[i] = inf;
	for (int i = 1; i <= k; i++)
		vis[ganran[i]] = 1;
	dist[1] = 0;
	qbian.push({0,1,0});
	int cent = 0;
	while (!qbian.empty()&&cent<n-k)
	{
		bian _top = qbian.top();
		qbian.pop();
		if (vis[_top.to])
		{
			continue;
		}
		cent++;
		vis[_top.to] = 1;
		//cout << _top.to << ' ' << dist[_top.to]<<'\n';
		for (auto son : e[_top.to])
		{
			if (!vis[son])
			{
				ll money = p;
				if (jiaqian[son])
					money = q;
				if (son == n)
					money = 0;
				if (dist[son] > dist[_top.to] + money)
				{
					dist[son] = dist[_top.to] + money;
					qbian.push({ _top.to,son,dist[son] });
				}
			}
		}
	}
}
int main()
{
	ios::sync_with_stdio(0);
	cin.tie(0), cout.tie(0);

	built();
	dijs();
	cout << dist[n];
	return 0;
}
2024/7/20 11:17
加载中...