裸dij,全T,蒟蒻在线求助
查看原帖
裸dij,全T,蒟蒻在线求助
524782
2_6HogCycle楼主2021/12/17 22:43
#include<iostream>
#include<cstring>
using namespace std;
int inf=0x3f3f3f3f;
int a,b,x,n,m;
int book[100001];
int u;
int dis[100001];
int min1;
int q1,q2,o,ans;
int head[100001];
int arr[100001];
int cnt,next1;
struct edge{
	int next;
	int to;
	int weight;
}edge[100001];
void add(int a,int b,int x)
{
	edge[++cnt].next=head[a];
	edge[cnt].to=b;
	edge[cnt].weight=x;
	head[a]=cnt;
}
int main()
{
	cin>>n>>m>>q1>>q2;
	memset(head,-1,sizeof(head));
	memset(edge,-1,sizeof(edge)); 
	memset(dis,inf,sizeof(dis));
	for(int i=1;i<=m;i++)
	{
		cin>>a>>b>>x;
		add(a,b,x);
		add(b,a,x);
	}	
	for(int i=head[1];i;i=edge[i].next)
	{
		next1=edge[i].to;
		dis[next1]=edge[i].weight;
	}
	dis[1]=0;
	book[1]=1;
	for(int i=1;i<=n-1;i++)
	{
		min1=inf;
		for(int j=1;j<=n;j++)
		{
			if(book[j]==0&&dis[j]<min1){
				min1=dis[j];
				u=j;		
			}				
		}
		book[u]=1;
		for(int k=head[u];k;k=edge[k].next)
		{
			next1=edge[k].to;
			if(dis[next1]>dis[u]+edge[k].weight)dis[next1]=dis[u]+edge[k].weight;														
		}
	}
	for(int i=1;i<=q1;i++)
	{
		cin>>o;
		if(dis[o]<=q2)arr[++ans]=i;
	}
	cout<<ans<<endl;
	for(int i=1;i<=ans;i++)
		cout<<arr[i]<<endl; 
	return 0;
 } 
2021/12/17 22:43
加载中...