样例能过,wa了51pts
查看原帖
样例能过,wa了51pts
1070708
Caged_Bird楼主2023/10/18 18:49
#include<bits/stdc++.h>
using namespace std;
struct node{
	int to,w;
};
vector<node>a[10005];
int dist[10005],n,m,c,e,t,ans[10005];
bool flag[10005];
node cow[10005];
int main(){
	memset(dist,0x7f,sizeof dist);
	cin>>n>>m>>c>>e;
	for(int i=1;i<=m;i++){
		int x,y,z;
		cin>>x>>y>>z;
		a[x].push_back(node{y,z});
		a[y].push_back(node{x,z});
	}
	for(int i=1;i<=c;i++){
		int x1;
		cin>>x1;
		cow[x1].to=1;
		cow[x1].w=i;	
	}
	dist[1]=0;
	for(int i=1;i<=n;i++){
		t=0;
		for(int j=1;j<=n;j++){
			if(!flag[j]&&dist[j]<dist[t])t=j;
		}
		flag[t]=1;
		for(int j=0;j<a[t].size();j++){
			dist[a[t][j].to]=min(dist[a[t][j].to],dist[t]+a[t][j].w);
		}
	}
	int r=1,cnt=0;
	for(int i=1;i<=n;i++){
		if(dist[i]<=e&&cow[i].to){
			cnt++;
			ans[r]=cow[i].w;
			r++;
		}
	}
	cout<<cnt<<endl;
	sort(ans+1,ans+r);
	for(int i=1;i<r;i++)cout<<ans[i]<<endl;
	return 0;
}

朴素dijkstra,不知道为啥wa

2023/10/18 18:49
加载中...