#include<bits/stdc++.h>
//#define int long long
#define pb push_back
#define fast ios_base::sync_with_stdio(false), cin.tie(nullptr), cout.tie(nullptr);
#define MOD 1000000007
#define inf 1e18
#define fi first
#define se second
#define FOR(i,a,b) for(int i=a;i<=b;i++)
#define FORD(i,a,b) for(int i=a;i>=b;i--)
#define sz(a) ((int)(a).size())
#define endl '\n'
#define pi 3.14159265359
#define TASKNAME "sightseeing"
using namespace std;
template<typename T> bool maximize(T &res, const T &val) { if (res < val){ res = val; return true; }; return false; }
template<typename T> bool minimize(T &res, const T &val) { if (res > val){ res = val; return true; }; return false; }
typedef pair<int,int> ii;
typedef pair<int,ii> iii;
typedef vector<int> vi;
const int MAXN = 5e6 + 9;
int n, m, k;
iii edge[MAXN];
struct DSU{
vector<int> lab;
DSU(int sz = 0){
lab.resize(sz + 9, -1);
}
int root(int u){
return (lab[u] < 0) ? u : lab[u] = root(lab[u]);
}
bool unite(int u, int v){
u = root(u);
v = root(v);
if (u != v){
if (lab[u] > lab[v]) swap(u, v);
lab[u] += lab[v];
lab[v] = u;
return true;
}
return false;
}
};
DSU D;
vector<int> g[MAXN];
int answer[MAXN];
void dfs(int u, int p, int d){
answer[u] = d;
for(int id: g[u]){
int w = edge[id].fi;
int v = edge[id].se.fi + edge[id].se.se - u;
if (v == p) continue;
dfs(v, u, min(d, w));
}
}
main()
{
fast;
if (fopen(TASKNAME".inp","r")){
freopen(TASKNAME".inp","r",stdin);
freopen(TASKNAME".out","w",stdout);
}
cin >> n >> m >> k;
FOR(i, 1, m){
cin >> edge[i].se.fi >> edge[i].se.se >> edge[i].fi;
}
sort(edge + 1, edge + 1 + m, [&](const iii &a, const iii &b){
return a.fi > b.fi;
});
D = DSU(n);
FOR(i,1, m){
if (D.unite(edge[i].se.fi, edge[i].se.se)){
g[edge[i].se.fi].pb(i);
g[edge[i].se.se].pb(i);
// cout << edge[i].se.se << ' ' << edge[i].se.fi<< endl;
}
}
dfs(1, -1, inf);
FOR(i, 1, k){
int u;
cin >> u;
cout << answer[u] << endl;
}
}
/**
Warning:
Cận lmao
Code imple thiếu case nào không.
Limit.
**/
Compilation message
sightseeing.cpp:62:1: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
62 | main()
| ^~~~
sightseeing.cpp: In function 'int main()':
sightseeing.cpp:6:13: warning: overflow in conversion from 'double' to 'int' changes value from '1.0e+18' to '2147483647' [-Woverflow]
6 | #define inf 1e18
| ^~~~
sightseeing.cpp:85:16: note: in expansion of macro 'inf'
85 | dfs(1, -1, inf);
| ^~~
sightseeing.cpp:66:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
66 | freopen(TASKNAME".inp","r",stdin);
| ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~
sightseeing.cpp:67:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
67 | freopen(TASKNAME".out","w",stdout);
| ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
55 ms |
117844 KB |
Output is correct |
| 2 |
Correct |
58 ms |
117840 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
57 ms |
117844 KB |
Output is correct |
| 2 |
Correct |
58 ms |
117844 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
75 ms |
119892 KB |
Output is correct |
| 2 |
Correct |
73 ms |
119632 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
971 ms |
219988 KB |
Output is correct |
| 2 |
Correct |
1467 ms |
262144 KB |
Output is correct |
