2023icpc南京站补题

vector<PII>e[N];
int n,m,c,minn,dist[N];
bool st[N];
void Dijkstra(int u){
	minn=1e18;
	for(int i=1;i<=n;i++)dist[i]=1e18,st[i]=0;
	priority_queue<PII,vector<PII>,greater<PII> >q;
	dist[u]=0;
	q.push({dist[u],u});
	while(q.size()){
		auto [dis,ver]=q.top();
		q.pop();
		if(st[ver])continue;
		st[ver]=1;
		for(auto [v,w]:e[ver]){
			if(v==u)minn=min(minn,dis+w);
			if(st[v])continue;
			if(dist[v]>dis+w){
				dist[v]=dis+w;
				q.push({dist[v],v});
			}
		}
	}
}
void solve(){
	cin>>n>>m>>c;
	int ans=0;
	for(int i=1;i<=m;i++){
		int u,v,z;cin>>u>>v>>z;
		e[u].pb({v,z});
		if(z<=c)ans=1;
	}
	for(int i=1;i<=n;i++){
		Dijkstra(i);
		if(minn<=c){ans=2;break;}
	}
	cout<<ans<<"\n";
}