{"problem":{"name":"[蓝桥杯 2023 省 A] 网络稳定性","description":{"content":"有一个局域网，由 $n$ 个设备和 $m$ 条物理连接组成，第 $i$ 条连接的稳定性为 $w_i$。 对于从设备 $A$ 到设备 $B$ 的一条经过了若干个物理连接的路径，我们记这条路径的稳定性为其经过所有连接中稳定性最低的那个。 我们记设备 $A$ 到设备 $B$ 之间通信的稳定性为 $A$ 至 $B$ 的所有可行路径的稳定性中最高的那一条。 给定局域网中的设备的物理连接情况，求出若干组","description_type":"Markdown"},"platform":"Luogu","limit":{"time_limit":1500,"memory_limit":262144},"difficulty":{"LuoguStyle":"P5"},"is_remote":true,"is_sync":true,"sync_url":null,"sign":"LGP9235"},"statements":[{"statement_type":"Markdown","content":"有一个局域网，由 $n$ 个设备和 $m$ 条物理连接组成，第 $i$ 条连接的稳定性为 $w_i$。\n\n对于从设备 $A$ 到设备 $B$ 的一条经过了若干个物理连接的路径，我们记这条路径的稳定性为其经过所有连接中稳定性最低的那个。\n\n我们记设备 $A$ 到设备 $B$ 之间通信的稳定性为 $A$ 至 $B$ 的所有可行路径的稳定性中最高的那一条。\n\n给定局域网中的设备的物理连接情况，求出若干组设备 $x_i$ 和 $y_i$ 之间的通信稳定性。如果两台设备之间不存在任何路径，请输出 $-1$。\n\n## Input\n\n输入的第一行包含三个整数 $n,m,q$，分别表示设备数、物理连接数和询问数。\n\n接下来 $m$ 行，每行包含三个整数 $u_i,v_i,w_i$，分别表示 $u_i$ 和 $v_i$ 之间有一条稳定性为 $w_i$ 的物理连接。\n\n接下来 $q$ 行，每行包含两个整数 $x_i,y_i$，表示查询 $x_i$ 和 $y_i$ 之间的通信稳定性。\n\n## Output\n\n输出 $q$ 行，每行包含一个整数依次表示每个询问的答案。\n\n[samples]\n\n## Note\n\n【评测用例规模与约定】\n\n对于 $30 \\%$ 的评测用例，$n,q \\leq 500$，$m \\leq 1000$；\n\n对于 $60 \\%$ 的评测用例，$n,q \\leq 5000$，$m \\leq 10000$；\n\n对于所有评测用例，$2 \\leq n,q \\leq 10^5$，$1 \\leq m \\leq 3 \\times 10^5$，$1 \\leq u_i,v_i,x_i,y_i \\leq n$，$\n1 \\leq w_i \\leq 10^6$，$u_i \\neq v_i$，$x_i \\neq y_i$。","is_translate":false,"language":"English"}],"meta":{"iden":"LGP9235","tags":["图论","贪心","倍增","并查集","2023","生成树","最近公共祖先 LCA","蓝桥杯省赛"],"sample_group":[["5 4 3\n1 2 5\n2 3 6\n3 4 1\n1 4 3\n1 5\n2 4\n1 3","-1\n3\n5"]],"created_at":"2026-03-03 11:09:25"}}