#include <cstdio>
#include <algorithm>
#include <vector>
#include <queue>
#include <utility>
using namespace std;
typedef pair<int,int> pi;
struct edge{int s,e,x;}a[5000005];
bool operator<(edge a, edge b){return a.x > b.x;}
struct disj{
int pa[500005], r[500005];
void init(int n){
for(int i=0; i<=n; i++) pa[i] = i;
}
int find(int x){
if(pa[x] == x) return x;
return pa[x] = find(pa[x]);
}
bool uni(int p, int q){
p = find(p);
q = find(q);
if(p == q) return 0;
if(r[p] < r[q]) pa[q] = p;
else pa[p] = q;
if(r[p] == r[q]) r[p]++;
return 1;
}
}disj;
int n,m,qr;
vector<pi> graph[500005];
queue<int> q,pa,d;
int ret[500005];
int main(){
scanf("%d %d %d",&n,&m,&qr);
for (int i=0; i<m; i++) {
scanf("%d %d %d",&a[i].s,&a[i].e,&a[i].x);
}
sort(a,a+m);
disj.init(n);
for (int i=0; i<m; i++) {
if(disj.uni(a[i].s,a[i].e)){
graph[a[i].s].push_back(pi(a[i].x,a[i].e));
graph[a[i].e].push_back(pi(a[i].x,a[i].s));
}
}
q.push(1);
pa.push(0);
d.push(1e9);
while (!q.empty()) {
int qf = q.front();
int pf = pa.front();
int df = d.front();
q.pop();
pa.pop();
d.pop();
ret[qf] = df;
for (int i=0; i<graph[qf].size(); i++) {
if(pf == graph[qf][i].second) continue;
q.push(graph[qf][i].second);
pa.push(qf);
d.push(min(graph[qf][i].first,df));
}
}
while (qr--) {
int t;
scanf("%d",&t);
printf("%d\n",ret[t]);
}
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
77760 KB |
Output is correct |
| 2 |
Correct |
0 ms |
77760 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
2 ms |
77760 KB |
Output is correct |
| 2 |
Correct |
2 ms |
77760 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
35 ms |
78948 KB |
Output is correct |
| 2 |
Correct |
28 ms |
78948 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1721 ms |
90960 KB |
Output is correct |
| 2 |
Correct |
2732 ms |
93468 KB |
Output is correct |
