42pts 跪求大佬调
查看原帖
42pts 跪求大佬调
1036693
carp_oier楼主2023/9/10 15:23

从第四个点开始 WA。

也很莫名,感觉算法很对,但代码算下来的结果就是不对。

#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define rl register ll

template <class T>

inline void read(T &res)
{
	char ch; bool f = 0;
	while((ch = getchar()) < '0' || ch > '9') f |= ch == '-';
	res = (ch ^ 48);
	while((ch = getchar()) <= '9' && ch >= '0') res = (res << 1) + (res << 3) + (ch ^ 48);
	res = f ? ~res + 1 : res;
}

inline void write(ll x)
{
	if(x < 0) x = -x, putchar('-');
	if(x > 9) write(x / 10);
	putchar(x % 10 + '0');
}

const ll N = 1e5 + 10, M = 4e5 + 10;

ll n, m, k, s, p, qq;

ll ne[M], e[M], w[N], h[N], tot, dis[N];

bool st[N], risk[N], vis[N];

struct node
{
	ll id, dis;
	bool operator <(const node &x) const
	{
		return dis > x.dis;
	}
};

priority_queue<node> q;

inline void dfs(ll u, ll cnt)
{
	if(cnt == s + 1) return ;
	
	if(cnt) vis[u] = 1; 
	
	for(rl i=h[u]; ~i; i = ne[i])
	{
		ll v = e[i];
		if(vis[v]) continue;
		
		dfs(v, cnt + 1);
	}
}

inline void add(ll a, ll b)
{
	ne[++tot] = h[a], h[a] = tot, e[tot] = b;
}

inline void dij()
{
	memset(dis, 0x7f, sizeof dis);
	memset(st, 0, sizeof st);
	
	dis[1] = 0;
	q.push({1, 0});
	
	while(q.size())
	{
		node asd = q.top();
		q.pop();
		ll u = asd.id;
		if(st[u]) continue;
		st[u] = 1;
		for(rl i=h[u]; ~i; i = ne[i])
		{
			ll v = e[i];
			if(dis[v] > dis[u] + w[v])
			{
				dis[v] = dis[u] + w[v];
				q.push({v, dis[v]});
			}
		}
	}
}

int main()
{
	freopen("1.in", "r", stdin);
	
	memset(h, -1, sizeof h);
	
	read(n), read(m), read(k), read(s);
	read(p), read(qq);
	
	for(rl i=1; i <= k; ++ i)
	{
		ll x;
		read(x);
		risk[x] = 1;
	}
	
	for(rl i=1; i <= m; ++ i)
	{
		ll a, b;
		read(a), read(b);
		add(a, b), add(b, a);
	}
	
	for(rl i=1; i <= n; ++ i)
		if(risk[i]) dfs(i, 0);
	
	for(rl i=1; i <= n; ++ i)
	{
		if(vis[i]) w[i] = qq;
		else w[i] = p;
		if(risk[i]) w[i] = 1e18;
	}
	
	dij();
	
	write(dis[n] - w[n]);
	return 0;
} 
2023/9/10 15:23
加载中...