O(Qnlogn)为什么会T!
查看原帖
O(Qnlogn)为什么会T!
1096250
Skyler_yunxi楼主2024/10/30 21:26

为什么!

#include<bits/stdc++.h>
namespace FAST_IO{
	char buf[1<<20],*p1,*p2,ch;
	int x,f;
	#define getchar() (p1==p2&&(p2=(p1=buf)+fread(buf,1,1<<20,stdin),p1==p2)?EOF:*p1++)
	inline int read(){
		x=f=0,ch=getchar();
		while(!isdigit(ch)){
			if(ch=='-')f=1;
			ch=getchar();
		}
		do x=(x<<1)+(x<<3)+(ch^48),ch=getchar();while(isdigit(ch));
		return f?-x:x;
	}
	inline void Write(register const int &p){
		if(9<p)Write((p>>1)/5);
		putchar(p%10|48);
	}
	inline void write(register const int &p,register const char c='\n'){if(p<0)putchar('-'),Write(-p);else Write(p);putchar(c);}
}
using FAST_IO::read;
using FAST_IO::write;
using namespace std;
struct node{
	int x,y;
}a[1005];
struct nb{
	int next,to,dis;
}e[40005];
int head[205],dis[205],vis[205],c,cnt,t[205];
void add(int u,int v,int d){
	e[cnt=-~cnt].dis=d;
	e[cnt].to=v;
	e[cnt].next=head[u];
	head[u]=cnt;
}
void up(struct node p){
	a[c=-~c]=p;
	for(register int i=c,j=c>>1;j;i=j,j>>=1){
		if(a[i].y<a[j].y)swap(a[i],a[j]);
		else break;
	}
}
void pop(){
	a[1]=a[c];
	c=~-c;
	for(register int i(1),j(2);j<=c;i=j,j<<=1){
		if(-~j<=c&&a[-~j].y<a[j].y)j=-~j;
		if(a[i].y>a[j].y)swap(a[i],a[j]);
		else break;
	}
}
int main(){
	register int n(read()),m(read()),Q;
	for(register int i(1);i^(-~n);i=-~i)
		t[i]=read();
	for(register int i(0);i^m;i=-~i){
		register const int tx(-~read()),ty(-~read()),tz(read());
		add(tx,ty,tz),add(ty,tx,tz);
	}
	Q=read();
	while(Q--){
		register const int x(-~read()),y(-~read()),T(read());
		if(t[x]>T||t[y]>T){
			puts("-1");
			continue;
		}
		memset(dis,127/3,sizeof(dis));
		memset(vis,0,sizeof(vis));
		dis[x]=c=0;
		up((struct node){x,0});
		struct node h;
		while(c){
			h=a[1];
			pop();
			if(vis[h.x])continue;
			vis[h.x]=1;
			for(register int i=head[h.x];i;i=e[i].next){
				if(t[e[i].to]>T)continue;
				if(dis[e[i].to]>dis[h.x]+e[i].dis){
					dis[e[i].to]=dis[h.x]+e[i].dis;
					if(!vis[e[i].to])up((struct node){e[i].to,dis[e[i].to]});
				}
			}
		}
		if(dis[y]>300000000)puts("-1");
		else write(dis[y]);
	}
	return 0;
}
2024/10/30 21:26
加载中...