Submission #2980542
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*&);
int findroot(int);
void mergeset(int,int);
vector<int>G[maxn],W[maxn];
vector<node*>v[maxn];
long long d[maxn],ds[maxn],c[maxn];
bool vis[maxn];
int p[maxn],depth[maxn],f[maxn][20],q[maxn];
int n,m,s,t;
int main(){
null->key=INF;
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;
c[x]=ds[x]+top(root[x]);
root[x]->lazy+=d[x]-d[p[x]];
root[p[x]]=merge(root[p[x]],root[x]);
}
for(int k=n-1;k;k--){
int x=q[k];
c[x]=max(c[x],c[p[x]]-(d[x]-d[p[x]])*2);
}
sort(q+1,q+n+1,[](int x,int y){return c[x]<c[y];});
memset(p,0,sizeof(p));
bool ok=false;
for(int k=1;k<=n;k++){
int x=q[k];
if(c[x]>=INF)break;
p[x]=x;
for(int i=0;i<(int)G[x].size();i++)
if(p[G[x][i]])mergeset(x,G[x][i]);
if(p[x]&&p[t]&&findroot(s)==findroot(t)){
printf("%lld\n",c[x]);
ok=true;
break;
}
}
if(!ok)printf("-1\n");
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;
}
int findroot(int x){return x==p[x]?x:p[x]=findroot(p[x]);}
void mergeset(int x,int y){p[findroot(x)]=findroot(y);}
Submission Info
Compile Error
./Main.cpp: In function ‘int main()’:
./Main.cpp:42: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:46: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
Set Name |
All |
Score / Max Score |
0 / 100 |
Status |
|
Set Name |
Test Cases |
All |
00_sample_00, 00_sample_01, 00_sample_02, 10_small_0, 10_small_1, 10_small_2, 10_small_3, 10_small_4, 10_small_5, 10_small_6, 10_small_7, 10_small_8, 10_small_9, 20_med_0, 20_med_1, 20_med_2, 20_med_3, 20_med_4, 20_med_5, 20_med_6, 21_med_0, 21_med_1, 21_med_2, 30_large_0, 30_large_1, 30_large_2, 30_large_3, 30_large_4, 30_large_5, 30_large_6, 31_large_0, 31_large_1, 31_large_2, 40_circle_0, 40_circle_1, 40_circle_2, 40_circle_3, 40_circle_4, 41_impossible_0, 41_impossible_1, 41_impossible_2, 42_special_0, 42_special_1, 42_special_10, 42_special_11, 42_special_12, 42_special_13, 42_special_14, 42_special_2, 42_special_3, 42_special_4, 42_special_5, 42_special_6, 42_special_7, 42_special_8, 42_special_9, 43_special_0, 43_special_1, 43_special_2, 43_special_3, 43_special_4, 43_special_5, 43_special_6, 43_special_7, 43_special_8, 43_special_9 |
Case Name |
Status |
Exec Time |
Memory |
00_sample_00 |
AC |
4 ms |
12544 KB |
00_sample_01 |
AC |
4 ms |
12544 KB |
00_sample_02 |
AC |
4 ms |
12544 KB |
10_small_0 |
AC |
4 ms |
12544 KB |
10_small_1 |
AC |
4 ms |
12544 KB |
10_small_2 |
AC |
4 ms |
12544 KB |
10_small_3 |
AC |
4 ms |
12544 KB |
10_small_4 |
AC |
4 ms |
12544 KB |
10_small_5 |
AC |
4 ms |
12544 KB |
10_small_6 |
AC |
4 ms |
12544 KB |
10_small_7 |
AC |
4 ms |
12544 KB |
10_small_8 |
AC |
4 ms |
12544 KB |
10_small_9 |
AC |
4 ms |
12544 KB |
20_med_0 |
AC |
111 ms |
31728 KB |
20_med_1 |
AC |
6 ms |
12800 KB |
20_med_2 |
AC |
42 ms |
19636 KB |
20_med_3 |
WA |
84 ms |
24920 KB |
20_med_4 |
WA |
116 ms |
31688 KB |
20_med_5 |
AC |
121 ms |
28880 KB |
20_med_6 |
WA |
62 ms |
23572 KB |
21_med_0 |
AC |
52 ms |
21680 KB |
21_med_1 |
AC |
123 ms |
28676 KB |
21_med_2 |
AC |
130 ms |
33068 KB |
30_large_0 |
AC |
125 ms |
29168 KB |
30_large_1 |
WA |
31 ms |
16920 KB |
30_large_2 |
WA |
64 ms |
22084 KB |
30_large_3 |
WA |
127 ms |
32340 KB |
30_large_4 |
WA |
64 ms |
20688 KB |
30_large_5 |
AC |
115 ms |
28216 KB |
30_large_6 |
AC |
138 ms |
32564 KB |
31_large_0 |
AC |
88 ms |
24556 KB |
31_large_1 |
AC |
151 ms |
32856 KB |
31_large_2 |
AC |
128 ms |
32388 KB |
40_circle_0 |
AC |
90 ms |
34176 KB |
40_circle_1 |
AC |
91 ms |
34176 KB |
40_circle_2 |
AC |
91 ms |
34176 KB |
40_circle_3 |
AC |
91 ms |
34176 KB |
40_circle_4 |
AC |
91 ms |
34176 KB |
41_impossible_0 |
AC |
318 ms |
44332 KB |
41_impossible_1 |
AC |
293 ms |
44588 KB |
41_impossible_2 |
AC |
288 ms |
44588 KB |
42_special_0 |
AC |
90 ms |
34176 KB |
42_special_1 |
AC |
95 ms |
34176 KB |
42_special_10 |
AC |
122 ms |
34176 KB |
42_special_11 |
AC |
129 ms |
34192 KB |
42_special_12 |
AC |
137 ms |
34240 KB |
42_special_13 |
AC |
146 ms |
34172 KB |
42_special_14 |
AC |
163 ms |
36276 KB |
42_special_2 |
AC |
100 ms |
34176 KB |
42_special_3 |
AC |
106 ms |
34176 KB |
42_special_4 |
AC |
108 ms |
34176 KB |
42_special_5 |
AC |
111 ms |
34176 KB |
42_special_6 |
AC |
112 ms |
34176 KB |
42_special_7 |
AC |
115 ms |
34176 KB |
42_special_8 |
AC |
115 ms |
34176 KB |
42_special_9 |
AC |
117 ms |
34176 KB |
43_special_0 |
WA |
120 ms |
34048 KB |
43_special_1 |
WA |
121 ms |
34048 KB |
43_special_2 |
WA |
119 ms |
34048 KB |
43_special_3 |
WA |
120 ms |
33920 KB |
43_special_4 |
WA |
120 ms |
33920 KB |
43_special_5 |
WA |
120 ms |
33920 KB |
43_special_6 |
WA |
120 ms |
33920 KB |
43_special_7 |
WA |
121 ms |
34048 KB |
43_special_8 |
WA |
122 ms |
33920 KB |
43_special_9 |
WA |
123 ms |
34048 KB |