A 国有 n 座城市，编号从 1 到 n，城市之间有 m 条双向道路。每一条道路对车辆都有重量限制，简称限重。现在有 q 辆货车在运输货物，司机们想知道每辆车在不超过车辆限重的情况下，最多能运多重的货物。

输入格式

输出格式

样例输入1[复制]

??4 3 1 2 4 2 3 3 3 1 1 31 3 1 4 1 3

样例输出1[复制]

3-13

每个测试点1s。

对于 30%的数据，0 < n < 1,000，0 < m < 10,000，0 < q < 1,000； 
对于 60%的数据，0 < n < 1,000，0 < m < 50,000，0 < q < 1,000； 
对于 100%的数据，0 < n < 10,000，0 < m < 50,000，0 < q < 30,000，0 ≤ z ≤ 100,000。

 1 #include<iostream> 2 #include<cstdio> 3 #include<cstring> 4 #include<algorithm> 5 using namespace std; 6  7 struct Edge 8 { 9     int u,v,w;10 }E[50000];11 12 struct Adj13 {14     int head,to,dist,next;15 }A[50000];16 17 int n,m,ans=0;18 int F[10000]={0};19 int Dir[10000]={0};20 bool Vis[10000]={0};21 22 bool cmp(Edge A,Edge B)23 {24     return A.w>B.w;25 }26 27 int find(int a)28 {29     while(F[a]!=0) a=F[a];30     return a;31 }32 33 int cnt=1;34 void add(int u,int v,int w)35 {36     A[cnt].next=A[u].head;37     A[cnt].to=v;38     A[cnt].dist=w;39     A[u].head=cnt++;40 }41 42 void dfs(int u)43 {44     Vis[u]=1;45     for(int i=A[u].head;i;i=A[i].next)46     {47         if(!Vis[A[i].to])48         {49             int v=A[i].to,w=A[i].dist;50             Dir[v]=min(Dir[u],w);51             dfs(v);52         }53     }54 }55 56 int main()57 {58     scanf("%d %d",&n,&m);59     for(int i=0;i<m;i++)60     {61         int x,y,z;62         scanf("%d %d %d",&x,&y,&z);63         E[i]={x,y,z};64     }65     sort(E,E+m,cmp);66     int num=n;67     for(int i=0;i<m&&num>0;i++)68     {69         int u=find(E[i].u);70         int v=find(E[i].v);71         if(u!=v)72         {73             F[u]=v;74             num--;75             add(E[i].u,E[i].v,E[i].w);76             add(E[i].v,E[i].u,E[i].w);77         }78     }79     int q;80     scanf("%d",&q);81     for(int i=0;i<q;i++)82     {83         int x,y;84         cin>>x>>y;85         if(find(x)!=find(y))86             printf("-1\n");87         else88         {89             memset(Vis,0,sizeof(Vis));90             memset(Dir,0x7f,sizeof(Dir));91             dfs(x);92             printf("%d\n",Dir[y]);93         }94     }95     return 0;96 }