题目描述

给定一个包含 n nn 个节点和 m mm 条边的图，每条边有一个权值。

你的任务是回答 k kk 个询问，每个询问包含两个正整数 s ss 和 t tt 表示起点和终点，要求寻找从 s ss 到 t tt 的一条路径，使得路径上权值最大的一条边权值最小。

输入格式

第一行包含三个整数 n nn、m mm、k kk，分别表示 n nn 个节点， m mm 条路径， k kk 个询问。

接下来 m mm 行，每行三个整数 u uu , v vv , w ww, 表示一个由 u uu 到 v vv 的长度为 w ww 的双向边。

再接下来 k kk 行，每行两个整数 s ss , t tt，表示询问从 s ss 连接到 t tt 的所有路径中单边长度最大值的最小值。

输出格式

输出包含 k kk 行，每一行包含一个整数 p pp 。p pp 表示 s ss 连接到 t tt 的所有路径中单边长度最大值的最小值。另外，如果 s ss 到 t tt 没有路径相连通，输出 -1 即可。

样例

样例输入

8 11 31 2 102 5 503 4 607 5 603 6 301 5 306 7 201 7 702 3 203 5 402 6 901 72 86 2

样例输出

30-130

数据范围与提示

对于 30% 30\%30% 的数据 n≤100,m≤1000,k≤100,w≤1000 n \leq 100, m \leq 1000, k \leq 100, w \leq 1000n≤100,m≤1000,k≤100,w≤1000 

对于 70% 70\%70% 的数据 n≤1000,m≤10000,k≤1000,w≤100000 n \leq 1000, m \leq 10000, k \leq 1000, w \leq 100000n≤1000,m≤10000,k≤1000,w≤100000 

对于 100% 100\%100% 的数据 n≤1000,m≤100000,k≤1000,w≤10000000 n \leq 1000, m \leq 100000, k \leq 1000, w \leq 10000000n≤1000,m≤100000,k≤1000,w≤10000000 

本题可能会有重边。

为了避免 Special Judge，本题所有的 w ww 均不相同。

题解：

同样是基于最小生成树，我们将其中关键信息保存

#include 
     
      using namespace std;const int MAXN=1000+10;const int INF=0x3f3f3f3f;int n,m,k;int mapp[MAXN][MAXN];int ans[MAXN][MAXN],dis[MAXN],pri[MAXN];bool vis[MAXN];void prim(){    memset(vis, false, sizeof(vis));    for (int i = 1; i <=n ; ++i)    {        dis[i]=INF;        pri[i]=i;    }    dis[1]=0;    for (int i = 1; i <=n ; ++i) {        int MAXX=INF,v=-1;        for (int j = 1; j <=n ; ++j) {            if(!vis[j]&&dis[j]
      
       z)            mapp[x][y]=mapp[y][x]=z;    }    prim();    while(k--)    {        scanf("%d%d",&x,&y);        printf("%d\n",ans[x][y]==0?-1:ans[x][y]);    }    return 0;}//int prim(int s)//{//    int res=0;//    memset(ans,0,sizeof(ans));// 初始化目标数组//    for(int i=1;i<=n;i++)//        vis[i] = false, d[i] = INF, pri[i]=i;//初始化 标记、距离、父亲数组。////    d[s]=0; // 自身的距离为零//    for(int i=0;i