求助HDU2066,悬关
  • 板块学术版
  • 楼主Dino_chx
  • 当前回复8
  • 已保存回复8
  • 发布时间2023/4/28 20:55
  • 上次更新2023/10/23 17:19:49
查看原帖
求助HDU2066,悬关
715233
Dino_chx楼主2023/4/28 20:55

蒟蒻调试了好几次都没有AC,求指点qwq


#include<bits/stdc++.h>
#define ll long long
#define inf LONG_LONG_MAX
using namespace std;
const int N=1e6+7; 
struct Edge
{
	int to,w,next;
}edge[N];
struct PE
{
	int to;
	ll dis;
	bool operator<(const PE &e)const
	{
		return dis>e.dis;
	}
};
int m,s,d,cntEdge,n=-1,head[N],went[N];
ll dist[N];
void insert(int u,int v,int w)
{
	edge[++cntEdge].to=v;
	edge[cntEdge].w=w;
	edge[cntEdge].next=head[u];
	head[u]=cntEdge;
	return;
}
void dijkstra(int starter)
{
	bitset<N> vis;
	priority_queue<PE> q; 
	while(!q.empty())
	{
		q.pop();
	}
	for(int i=0;i<=n;i++)
	{
		dist[i]=inf;
	}
	vis.reset();
	dist[starter]=0;
	q.push((PE){starter,dist[starter]});
	while(!q.empty())
	{
		PE top=q.top();
		q.pop();
		int x=top.to;
		if(vis[x])
			continue;
		vis[x]=1;
		for(int i=head[x];i;i=edge[i].next)
		{
			int to=edge[i].to,w=edge[i].w;
			if(dist[x]+w<dist[to])
			{
				dist[to]=dist[x]+w;
				if(!vis[to])
					q.push((PE){to,dist[to]});
			}
		}
	}
	return;
}
void init()
{
	n=-1;
	memset(head,0,sizeof head);
	cntEdge=0;
	memset(edge,0,sizeof edge);
	memset(went,0,sizeof went);
	return;
}
int main()
{
	while(scanf("%d%d%d",&m,&s,&d)!=EOF)
	{
		for(int i=1,u,v,w;i<=m;i++)
		{
			scanf("%d%d%d",&u,&v,&w);
			insert(u,v,w);
			insert(v,u,w);
			n=max({n,u,v});
		}
		for(int i=1,link;i<=s;i++)
		{
			scanf("%d",&link);
			insert(0,link,0);
			insert(link,0,0);
		}
		for(int i=1;i<=d;i++)
		{
			scanf("%d",&went[i]);
		}
		dijkstra(0);
		ll minn=inf;
		for(int i=1;i<=d;i++)
		{
			minn=min(minn,dist[went[i]]);
		}
		printf("%lld\n",minn); 
	}
	return 0;
}

2023/4/28 20:55
加载中...