# Cod sursa(job #2833713)

Utilizator Data 15 ianuarie 2022 15:35:55 Radiatie 40 cpp-64 done Arhiva de probleme 1.9 kb
``````#include <iostream>
#include <fstream>
#include <vector>
#include <algorithm>
#include <unordered_map>

using namespace std;

int n, m, k, a, b, c, root[15005], minlen[15005];
vector<pair<int, pair<int, int>>> edges;
vector<pair<int, int>> G[15005];
vector<pair<int, int>> queries, qcpy;
unordered_map<int, unordered_map<int, int>> umap;

int getRoot(int x)
{
if ( x != root[x] )
root[x] = getRoot(root[x]);
return root[x];
}

{
root[y] = x;
}

void dfs(int x, int p)
{
for ( auto pa : G[x] )
if ( pa.first != p )
{
// cout << x << " >> " << pa.first << "\n";
minlen[pa.first] = max(minlen[x], pa.second);
dfs(pa.first, x);
}
}

int main()
{
fin >> n >> m >> k;
for ( int i = 1; i <= n; i++ )
root[i] = i;

for ( int i = 1; i <= m; i++ )
{
fin >> a >> b >> c;
edges.push_back({ c, {a, b} });
}

sort(edges.begin(), edges.end());

for ( auto edge : edges )
{
a = getRoot(edge.second.first);
b = getRoot(edge.second.second);

if ( a != b )
{
G[a].push_back({ b, edge.first });
G[b].push_back({ a, edge.first });
}
}

edges.clear();

for ( int i = 1; i <= k; i++ )
{
fin >> a >> b;
queries.push_back({ min(a, b), max(a, b) });
}
qcpy = queries;
sort(queries.begin(), queries.end());
int last = 0;

for ( auto query : queries )
{
if ( last != query.first )
{
for ( int i = 1; i <= n; i++ )
minlen[i] = 0;
dfs(query.first, 0);
}
last = query.first;
umap[query.first][query.second] = minlen[query.second];
}

for ( auto query : qcpy )
fout << umap[query.first][query.second] << "\n";
}
``````