目标30pts 暴力n^3做法 实际得分10pts 求改
查看原帖
目标30pts 暴力n^3做法 实际得分10pts 求改
573589
ande楼主2022/10/1 19:19

RT 想求暴力错哪了

#include<bits/stdc++.h>
using namespace std;
#define int long long
const int N = 1e4+10;
inline int read(){
	int x = 0, f = 1;
	char ch = getchar();
	while(ch < '0' || ch > '9'){if(ch == '-') f = -1; ch = getchar();}
	while(ch >= '0' && ch <= '9'){x = (x << 3) + (x << 1) + (ch - 48); ch = getchar();}
	return x * f; 
}
int dis[N][N],ans;
int n,m; 
signed main(){
	n = read(), m = read();
	for(int i = 1;i <= m;i++){
		int x = read(), y = read(),z = read();
		if(dis[x][y] || dis[y][x] )
			dis[x][y] = dis[y][x] = max(z,dis[x][y]);
		else 
			dis[x][y] = dis[y][x]  = z;
		}
	
	for(int i = 1;i <= n;i++){
		for(int j = 1;j <= n;j++){
			for(int z = 1;z <= n;z++){
				if(dis[i][z] == 0 || dis[z][j] == 0)continue;
				dis[i][j] = dis[j][i] = max(dis[i][j],min(dis[i][z],dis[z][j]));
			}
		}
	}
	int q = read(); //cout<<"-10";
	while(q--){
		int x = read(),y = read();
		if(dis[x][y] == 0)printf("-1\n");
		else printf("%lld\n",dis[x][y]); 
	}
//	system("pause"); 
return 0;
}
//	6 5
//	1 3 3
//	2 4 1
//	1 2 3
//	3 4 3
//	1 5 6
//	2
//	1 4
//	1 6
2022/10/1 19:19
加载中...