wcx tql
by Protons @ 2019-03-09 09:26:15
。。。
by 公主殿下MIKU @ 2019-03-09 09:26:52
~~为什么我交上去就是0分~~
检查数组大小，似乎有问题
by Hope2075 @ 2019-03-09 09:28:33
@[公主殿下MIKU](/space/show?uid=113773)
怎么回事，你代码给我一交WA光了。
by Smile_Cindy @ 2019-03-09 09:29:00
@[i_m_a_](/space/show?uid=86649)
没有吧，最后一个是wa，不是mle
by 公主殿下MIKU @ 2019-03-09 09:29:08
~~怎么棕了~~（危险发言）
by AuCloud @ 2019-03-09 09:32:02
@[Alpha](/space/show?uid=87058) @[i_m_a_](/space/show?uid=86649)
粘错代码了
```cpp
#include<iostream>
#include<cstdio>
#include<cctype>
#include<algorithm>
using namespace std;
int n,m,x,y,z,q;
int read() {
int ret=0;
char ch=getchar();
while (ch<='9'&&ch>='0') {
ret=ret*10+ch-48;
ch=getchar();
}
return ret;
}
struct node1 {
int l,r,dis;
} edg1[500000>>1|1];
struct node {
int to,dis,nxt;
} edg2[500000>>1|1];
int f[100001];
bool vis[100001];
int find(int root) {
return f[root]==root?root:f[root]=find(f[root]);
}
bool cmp(node1 a,node1 b) {
return a.dis>b.dis;
}
int head[100001],num;
void add(int x,int y,int z) {
edg2[++num].to=y;
edg2[num].nxt=head[x];
edg2[num].dis=z;
head[x]=num;
}
int deep[500001],fa[500001][50],lg[500001],dis[500001];
void dfs(int x,int y) {
deep[x]=deep[y]+1;
fa[x][0]=y;
for(int i=1; (1<<i)<=deep[x]; i++)
fa[x][i]=fa[fa[x][i-1]][i-1];
for(int i=head[x]; i; i=edg2[i].nxt)
if(edg2[i].to!=y) {
dis[edg2[i].to]=edg2[i].dis;
dfs(edg2[i].to,x);
}
}
int lca(int x,int y) {
if(deep[x]<deep[y])
swap(x,y);
while(deep[x]>deep[y])
x=fa[x][lg[deep[x]-deep[y]]-1];
if(x==y)
return x;
for(int k=lg[deep[x]]-1; k>=0; k--)
if(fa[x][k]!=fa[y][k])
x=fa[x][k],y=fa[y][k];
return fa[x][0];
}
int ans(int x,int y) {
int a=2147483647,b=a;
int last=lca(x,y);
for(int i=x; i!=last; i=fa[i][0])
a=min(a,dis[i]);
for(int i=y; i!=last; i=fa[i][0])
b=min(b,dis[i]);
return min(a,b);
}
int main() {
n=read();
m=read();
for(int i=1; i<=n; i++)
f[i]=i;
for(int i=1; i<=m; i++) {
edg1[i].l=read();
edg1[i].r=read();
edg1[i].dis=read();
}
sort(edg1+1,edg1+m+1,cmp);
for(int i=1; i<=m; i++) {
int ls=find(edg1[i].l);
int rs=find(edg1[i].r);
if(ls!=rs) {
add(f[ls],rs,edg1[i].dis);
add(rs,f[ls],edg1[i].dis);
f[ls]=rs;
}
}
for(int i=1; i<=n; i++)
lg[i]=lg[i-1]+(i==1<<lg[i-1]);
for(int i=1; i<=n; i++) {
if(!deep[i])
dfs(i,0);
}
q=read();
for(int i=1; i<=q; i++) {
x=read();
y=read();
if(find(x)!=find(y)) printf("-1\n");
else printf("%d\n",ans(x,y));
}
return 0;
}
```
by 公主殿下MIKU @ 2019-03-09 09:32:54
@[Alpha](/space/show?uid=87058) @i_ma
看看哪里错了
by 公主殿下MIKU @ 2019-03-09 09:35:00
@[公主殿下MIKU](/space/show?uid=113773)
为什么这组数据你输出全是-1？
```
7 8
1 2 2
1 3 5
3 4 4
4 4 2
3 5 3
6 7 4
1 3 3
4 5 8
8
1 2
1 4
1 3
1 5
1 6
2 5
3 5
6 7
```
stdout:
```
2
4
5
4
-1
2
4
4
```
by Smile_Cindy @ 2019-03-09 09:37:00
@[Alpha](/space/show?uid=87058)
不知道哎
by 公主殿下MIKU @ 2019-03-09 09:38:35