• 微信公众号:美女很有趣。 工作之余,放松一下,关注即送10G+美女照片!

做题记录 Luogu P5304

开发技术 开发技术 4小时前 2次浏览

P5304 [GXOI/GZOI2019]旅行者 – 洛谷 | 计算机科学教育新生态 (luogu.com.cn)

特殊处理的 dijkstrar。

#include<bits/stdc++.h>
using namespace std;
#define int long long
#define inf 0x1f1f1f1f1f1f1f1f
#define N 4000005
int n, m, k;
struct node
{
	int val, num, from;
};
bool operator < (node a, node b)
{
	return a.val > b.val;
}
priority_queue<node> q;
node dis[N], dis1[N];
int first[N], Next[N], to[N], w[N], tot;
int uu[N], vv[N], ww[N];
int vis[N], a[N];
void add(int x, int y, int z)
{
	Next[++tot] = first[x];
	first[x] = tot;
	to[tot] = y;
	w[tot] = z;
	return;
}
void dijkstrar()
{
	memset(vis, 0, sizeof(vis));
	for(int i = 1; i <= n; i++)
	{
		dis[i].val = inf;
		dis[i].num = -1;
		dis[i].from = -1;
	}
	for(int i = 1; i <= k; i++)
	{
		dis[a[i]].val = 0;
		dis[a[i]].num = a[i];
		dis[a[i]].from = a[i];
		q.push(dis[a[i]]);
	}
	while(!q.empty())
	{
		node u = q.top();
		q.pop();
		if(vis[u.num])
		{
			continue;
		}
		vis[u.num] = 1;
		for(int i = first[u.num]; i; i = Next[i])
		{
			int v = to[i];
			if(u.val + w[i] < dis[v].val)
			{
				dis[v].val = u.val + w[i];
				dis[v].num = v;
				dis[v].from = u.from;
				q.push(dis[v]);
			}
		}
	}
	return;
}
signed main()
{
	//freopen("tour.in", "r", stdin);
	//freopen("tour.out", "w", stdout);
	int T;
	scanf("%lld", &T);
	while(T--)
	{
		tot = 0;
		memset(first, 0, sizeof(first));
		scanf("%lld%lld%lld", &n, &m, &k);
		for(int i = 1; i <= m; i++)
		{
			scanf("%lld%lld%lld", &uu[i], &vv[i], &ww[i]);
			add(uu[i], vv[i], ww[i]);
		}
		for(int i = 1; i <= k; i++)
		{
			scanf("%lld", &a[i]);
		}
		dijkstrar();
		for(int i = 1; i <= n; i++)
		{
			dis1[i] = dis[i];
		}
		tot = 0;
		memset(first, 0, sizeof(first));
		for(int i = 1; i <= m; i++)
		{
			add(vv[i], uu[i], ww[i]);
		}
		dijkstrar();
		int ans = inf;
		for(int i = 1; i <= m; i++)
		{
			if(dis1[uu[i]].from != dis[vv[i]].from)
			{
				ans = min(ans, dis1[uu[i]].val + dis[vv[i]].val + w[i]);
			}
		}
		printf("%lldn", ans);
	}
	return 0;
}

程序员灯塔
转载请注明原文链接:做题记录 Luogu P5304
喜欢 (0)