제출 #1174453

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1174453		khangrl	관광 (NOI14_sightseeing)	C++20	25 / 25	1827 ms	217036 KiB

sightseeing

#include<bits/stdc++.h>
#define ff first
#define ss second
#define int long long
#define pb push_back
using namespace std;
int n, m, q, par[500005];
bool vis[500005];
vector <int> dist(500005, 1e9);
vector <pair <int, int> > path[500005];
vector <pair <int, pair <int, int> > > v;
int find(int x){
	if(x==par[x]){
		return x;
	}
	else{
		par[x]=find(par[x]);
		return par[x];
	}
}
int same(int x, int y){
	if(find(x)==find(y)){
		return 1;
	}
	return 0;
}
void join(int x, int y){
	x=find(x);
	y=find(y);
	par[y]=x;
}
void dfs(int nw, int lngth){
	dist[nw]=min(lngth, dist[nw]);
	for(auto k:path[nw]){
		int nx=k.ff, w=k.ss;
		if(!vis[nx]){
			vis[nx]=1;
			dfs(nx, min(lngth, w));
		}
	}
}
signed main(){
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
	cin>>n>>m>>q;
	for(int i=1; i<=n; i++) par[i]=i;
	for(int i=1; i<=m; i++){
		int a, b, w;
		cin>>a>>b>>w;
		v.pb({w, {a, b}});
	}
	sort(v.begin(), v.end(), greater <pair <int, pair <int, int> > >());
	for(int i=0; i<m; i++){
		int w=v[i].ff, a=v[i].ss.ff, b=v[i].ss.ss;
		if(!same(a, b)){
			join(a, b);
			path[a].pb({b, w});
			path[b].pb({a, w});
		}
	}
	dfs(1, 1e9);
	while(q--){
		int k;
		cin>>k;
		cout<<dist[k]<<endl;
	}
}

• Subtask 1: 4 / 4
• Subtask 2: 5 / 5
• Subtask 3: 6 / 6
• Subtask 4: 10 / 10