萌新袜子求卡常,就只T了倒数第三,四个点
查看原帖
萌新袜子求卡常,就只T了倒数第三,四个点
754467
f_hxr_楼主2024/6/2 18:02

rt,不知道这数据加了什么奇奇怪怪的东西不会卡最短路吧

//I AK 雷石东直放站题 
#include <bits/stdc++.h>
using namespace std;
namespace IO{
	char buff[1<<21],*p1=buff,*p2=buff;
	#define getch() (p1==p2&&(p2=((p1=buff)+fread(buff,1,1<<21,stdin)),p1==p2)?EOF:*p1++)
	template<typename T>
	void read(T &x) {char ch=getch();int fl=1;x=0;while(ch>'9'||ch<'0'){if(ch=='-')fl=-1;ch=getch();}while(ch<='9'&&ch>='0') {x=x*10+ch-48;ch=getch();}x*=fl;}
	template<typename T,typename ...Args>
	void read(T &x,Args& ...args){read(x);read(args...);}
	char obuf[1<<21],*p3=obuf;
	inline void putch(char ch){if(p3-obuf<(1<<21))*p3++=ch;else fwrite(obuf,p3-obuf,1,stdout),p3=obuf,*p3++=ch;}
	char ch[100]; template<typename T>
	void write(T x){if(!x)return putch('0');if(x<0)putch('-'),x*=-1;int top=0;while(x)ch[++top]=x%10+48,x/=10;while(top)putch(ch[top]),top--;}
	template<typename T,typename ...Args>
	void write(T x,Args ...args){write(x);write(args...);}
	inline void flush(){fwrite(obuf,p3-obuf,1,stdout);}
}using namespace IO;
const int maxn=5e5+7;
typedef long long LL;
const LL inf=0x7f7f7f7f7f7f7f7f;
LL N,M,S,T,L,K,ans;
int head[maxn<<1],nxt[maxn<<1],to[maxn<<1],cnt_edge;
LL weight[maxn<<1];
void AddEdge(int u,int v,LL w){nxt[++cnt_edge]=head[u];to[cnt_edge]=v;head[u]=cnt_edge;weight[cnt_edge]=w;}
LL dist[maxn][2],vis[maxn];
void init(int from,int op){
	memset(vis,0,sizeof(vis));
	priority_queue<pair<LL,int> >q;
	dist[from][op]=0;q.push(make_pair(0,from));
	while(!q.empty()){
		int x=q.top().second;q.pop();
		vis[x]=1;
		for(int i=head[x];i;i=nxt[i]){
			if(dist[x][op]+weight[i]<dist[to[i]][op]){
				dist[to[i]][op]=dist[x][op]+weight[i];
				if(!vis[to[i]])q.push(make_pair(-dist[to[i]][op],to[i]));
			}
		}
	}
}
LL un[maxn*2+7],UN;
#define get(xx) (upper_bound(un+1,un+UN+1,xx)-un-1)
struct BIT{
	LL DAT[maxn+514],CZ=maxn+114;
	void Add(int inx,LL xx){++inx;for(;inx<=CZ;inx+=inx&-inx)DAT[inx]+=xx;}
	LL Sum(int inx){++inx;LL ret=0;for(;inx;inx-=inx&-inx)ret+=DAT[inx];return ret;}
}BIT1,BIT2,BIT3;
struct OP{LL X,Y,type;}O[maxn*2+114]; 
bool cmp(OP A,OP B){return A.X==B.X?A.Y<B.Y:A.X<B.X;}
int cntO;
int main(){
	//freopen("P10206_87.in","r",stdin);
	//freopen("P10206.out","w",stdout);
	memset(dist,0x7f,sizeof(dist));
	read(N,M,S,T,L,K);
	for(LL i=1,u,v,w;i<=M;++i){read(u,v,w);AddEdge(u,v,w);AddEdge(v,u,w);}
	init(S,0);
	if(dist[T][0]<=K){write(N*(N-1)>>1);flush();return 0;}
	if(L>K){putch('0');flush();return 0;}
	init(T,1);
	for(int i=1;i<=N;i++)un[++UN]=dist[i][0],un[++UN]=dist[i][1];
	un[++UN]=-inf;un[++UN]=inf;
	sort(un+1,un+UN+1);UN=unique(un+1,un+UN+1)-un-1;
	for(int i=1;i<=N;i++)
		BIT1.Add(get(dist[i][0]),1),BIT2.Add(get(dist[i][1]),1);
	for(int i=1;i<=N;i++){
		LL val1=K-dist[i][1]-L;
		LL val2=K-dist[i][0]-L;
		ans+=BIT1.Sum(get(val1))-(dist[i][0]<=val1);
		ans+=BIT2.Sum(get(val2))-(dist[i][1]<=val2);
	}
	LL tmp=0;
	for(int i=1;i<=N;i++){
		O[++cntO].X=get(dist[i][0]);
		O[cntO].Y=get(dist[i][1]);
		O[cntO].type=0;
		O[++cntO].X=get(K-dist[i][0]-L);
		O[cntO].Y=get(K-dist[i][1]-L);
		O[cntO].type=1;
	}
	sort(O+1,O+cntO+1,cmp);
	for(int i=1;i<=cntO;i++){
		if(O[i].type==0){BIT3.Add(O[i].Y,1);}
		else{tmp+=BIT3.Sum(O[i].Y);}
	} 
	ans>>=1;ans-=tmp;
	write(ans);flush();
	return 0;
}
2024/6/2 18:02
加载中...