Submission #2980135

---

Source Code Expand

#include<bits/stdc++.h>
using namespace std;
const int maxn=100005,maxm=200005;
const long long INF=200000000000000ll;
struct A{
	int x;
	long long d;
	A(int x,long long d):x(x),d(d){}
	bool operator<(const A &a)const{return d>a.d;}
};
struct node{
	long long key,lazy;
	bool bad;
	int d;
	node *lc,*rc;
	node(){}
	node(long long key):key(key),lazy(0),bad(false),d(0){}
	void pushdown(){
		if(!lazy)return;
		key+=lazy;
		lc->lazy+=lazy;
		rc->lazy+=lazy;
		lazy=0;
	}
	void refresh(){d=rc->d+1;}
}null[maxm<<1],*ptr=null,*root[maxn];
void Dijkstra(int);
int LCA(int,int);
node *newnode(long long);
node *merge(node*,node*);
long long top(node*&);
vector<int>G[maxn],W[maxn];
vector<node*>v[maxn];
long long d[maxn],ds[maxn];
bool vis[maxn];
long long ans=0;
int p[maxn],depth[maxn],f[maxn][20],q[maxn];
int n,m,s,t;
int main(){
	null->key=0x3f3f3f3f3f3f3f3fll;
	scanf("%d%d%d%d",&n,&m,&s,&t);
	for(int i=0;i<=n;i++)root[i]=null;
	while(m--){
		int x,y,z;
		scanf("%d%d%d",&x,&y,&z);
		G[x].push_back(y);
		W[x].push_back(z);
		G[y].push_back(x);
		W[y].push_back(z);
	}
	Dijkstra(s);
	memcpy(ds,d,sizeof(d));
	Dijkstra(t);
	for(int i=1;i<=n;i++)
		f[i][0]=p[i];
	for(int j=1;(1<<j)<n;j++)
		for(int i=1;i<=n;i++)
			f[i][j]=f[f[i][j-1]][j-1];
	memset(vis,0,sizeof(vis));
	for(int x=1;x<=n;x++)
		if(d[x]<INF){
			for(int i=0;i<(int)G[x].size();i++){
				if(!vis[x]&&G[x][i]==p[x]&&W[x][i]==d[x]-d[p[x]]){
					vis[x]=true;
					continue;
				}
				root[x]=merge(root[x],newnode(d[G[x][i]]+W[x][i]));
				int u=LCA(x,G[x][i]);
				v[u].push_back(ptr);
			}
		}
	for(int i=1;i<=n;i++)q[i]=i;
	sort(q+1,q+n+1,[](int x,int y){return d[x]>d[y];});
	for(int k=1;k<n;k++){
		int x=q[k];
		for(auto t:v[x])t->bad=true;
		ans=max(ans,ds[x]+top(root[x]));
		root[x]->lazy+=d[x]-d[p[x]];
		root[p[x]]=merge(root[p[x]],root[x]);
	}
	if(ans>=INF)ans=-1;
	printf("%lld\n",ans);
	return 0;
}
void Dijkstra(int s){
	for(int i=1;i<=n;i++)d[i]=INF;
	memset(vis,0,sizeof(vis));
	memset(p,0,sizeof(p));
	memset(depth,0,sizeof(depth));
	d[s]=0;
	priority_queue<A>heap;
	heap.push(A(s,0));
	while(!heap.empty()){
		int x=heap.top().x;
		heap.pop();
		if(vis[x])continue;
		vis[x]=true;
		depth[x]=depth[p[x]]+1;
		for(int i=0;i<(int)G[x].size();i++)
			if(!vis[G[x][i]]&&d[G[x][i]]>d[x]+W[x][i]){
				d[G[x][i]]=d[x]+W[x][i];
				p[G[x][i]]=x;
				heap.push(A(G[x][i],d[G[x][i]]));
			}
	}
}
int LCA(int x,int y){
	if(depth[x]!=depth[y]){
		if(depth[x]<depth[y])swap(x,y);
		int t=depth[x]-depth[y];
		for(int i=19;~i;i--)
			if((t>>i)&1)x=f[x][i];
	}
	if(x==y)return x;
	for(int i=19;~i;i--)
		if(f[x][i]!=f[y][i]){
			x=f[x][i];
			y=f[y][i];
		}
	return f[x][0];
}
node *newnode(long long key){
	*++ptr=node(key);
	ptr->lc=ptr->rc=null;
	return ptr;
}
node *merge(node *x,node *y){
	if(x==null)return y;
	if(y==null)return x;
	x->pushdown();
	y->pushdown();
	if(x->key>y->key)swap(x,y);
	x->rc=merge(x->rc,y);
	if(x->rc->d>x->lc->d)swap(x->lc,x->rc);
	x->refresh();
	return x;
}
long long top(node *&x){
	while(x!=null&&x->bad){
		x->pushdown();
		x=merge(x->lc,x->rc);
	}
	if(x!=null)x->pushdown();
	return x->key;
}

Submission Info

Compile Error

./Main.cpp: In function ‘int main()’:
./Main.cpp:41:31: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d%d%d%d",&n,&m,&s,&t);
                               ^
./Main.cpp:45:27: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d%d%d",&x,&y,&z);
                           ^

Judge Result