社区讨论

求大佬卡下常

P1119灾后重建参与者 3已保存回复 4

讨论操作

快速查看讨论及其快照的属性,并进行相关操作。

当前回复
4 条
当前快照
1 份
快照标识符
@lo2d7oey
此快照首次捕获于
2023/10/23 11:55
2 年前
此快照最后确认于
2023/11/03 12:03
2 年前
查看原帖
O2O_2: 100pts.
不开 O2O_2 :90pts.
真是个好氧,优化了大约10倍时间复杂度.
CPP
#include<bits/stdc++.h>
using namespace std;
#define Min(x,y) ((x)<(y) ? (x) : (y))
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*10+ch-48;ch=getchar();}
	return x*f;
}
int n,m;
int t[210];
int e[210][210];
int nxt=1;
int main() {
	n=read(),m=read();
	memset(e,0x3f,sizeof e);
	for(int i=1;i<=n;i++) t[i]=read();
	for(int i=1;i<=m;i++){
		int u=read(),v=read(),w=read();
		u++,v++;
		e[u][v]=e[v][u]=w;
	}
	int q=read();
	while(q--){
		int x,y,t0;
		x=read(),y=read(),t0=read();
		x++,y++;
		for(int k=nxt;k<=n;k++){
			if(t[k]>t0){
				nxt=k;
				break;
			}
			for(int i=1;i<=n;i++)
				for(int j=1;j<=n;j++)
					e[i][j]=Min(e[i][k]+e[k][j],e[i][j]);
		}
		if(t[x]>t0 || t[y]>t0 || e[x][y]==0x3f3f3f3f)
		    printf("-1\n");
		else printf("%d\n",e[x][y]);
	}
	return 0;
} 

回复

4 条回复,欢迎继续交流。

正在加载回复...