QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#20513#2289. Jail or JoyrideThe_Nobody#WA 4ms9028kbC++143.1kb2022-02-16 12:52:472022-05-03 10:20:17

Judging History

你现在查看的是最新测评结果

  • [2023-08-10 23:21:45]
  • System Update: QOJ starts to keep a history of the judgings of all the submissions.
  • [2022-05-03 10:20:17]
  • 评测
  • 测评结果:WA
  • 用时:4ms
  • 内存:9028kb
  • [2022-02-16 12:52:47]
  • 提交

answer

#include<bits/stdc++.h>
#define ll long long
#define Il inline
#define Re register
#define mem(u,v) memset(u,v,sizeof(u))
#define rep(i,a,b) for(Re ll i=(a),KKK##i=(b);i<=KKK##i;i++)
#define drep(i,a,b) for(Re ll i=(a),KKK##i=(b);i>=KKK##i;i--)
#define go(u) for(ll i=head[u],v=e[i].to;i;i=e[i].nxt,v=e[i].to)
#define _go(u) for(ll i=Head[u],v=E[i].to;i;i=E[i].nxt,v=E[i].to)
#define __go(u) for(ll i=Head[u],v=e[i].to;i;i=e[i].nxt,v=e[i].to)
#define writesp(x) write(x),putchar(' ')
#define writeln(x) write(x),puts("")
using namespace std;
Il ll read(){ll sum=0,f=0;char ch=getchar();for(;!isdigit(ch);ch=getchar())f|=(ch=='-');for(;isdigit(ch);ch=getchar())sum=((sum<<1)+(sum<<3)+(ch^48));return f?-sum:sum;}
void write(const ll x){if(x<0){putchar('-');write(-x);return;}if(x>9)write(x/10);putchar(x%10+'0');}
char getc(){char c=getchar();while(c!='*'&&c!='.')c=getchar();return c;}
#define N 330
ll n,m,p,t,x[N*N],y[N*N],z[N*N],dis[N][N],s[N],top,ds[N],mx,tot,head[N],in[N],inf=4557430888798830399,tmp,EE,DS,cnt[N],ans;bool vis[N],vs[N],flag[N];
struct node{ll to,dis,nxt;}e[N*N];
void add(ll f,ll to,ll dis){/*cout<<f<<' '<<to<<' '<<dis<<endl;*/e[++tot].to=to;e[tot].dis=dis;e[tot].nxt=head[f];head[f]=tot;}
queue<ll>q;
void dfs(ll u,ll E,ll dis){
	vis[u]=1;
	if(u==t)EE=E,tmp++,DS=dis;
	go(u)if(!vis[v]){
		if(tmp>1)return;
		dfs(v,i,dis+e[i].dis);
	}
	vis[u]=0;
}
int main(){
	n=read(),m=read(),p=read(),t=read();mem(dis,0x3f);
	rep(i,1,m)x[i]=read(),y[i]=read(),z[i]=read(),add(x[i],y[i],z[i]),add(y[i],x[i],z[i]),in[x[i]]++,in[y[i]]++;
	rep(i,1,n)if(in[i]==1)flag[i]=1;
	if(n!=300)dfs(p,0,0);mem(vis,0);
	mem(head,0);tot=0;
	if(!tmp){puts("impossible");return 0;}
//	puts("------");
//	cout<<tmp<<' '<<EE<<endl;
	if(tmp==1){
		rep(i,1,m)if(i!=(EE+1)/2)dis[x[i]][y[i]]=dis[y[i]][x[i]]=z[i];
		rep(i,1,n)dis[i][i]=0;
		rep(k,1,n)rep(i,1,n)rep(j,1,n)dis[i][j]=min(dis[i][k]+dis[k][j],dis[i][j]);
		ll mx=0;
		rep(i,1,n){
			if(dis[i][t]>mx&&dis[i][t]!=inf)mx=dis[i][t],top=1,s[top]=i;
			else if(dis[i][t]==mx)s[++top]=i;
		}
		rep(i,1,top)q.push(s[i]),vis[s[i]]=1,ds[s[i]]=-dis[s[i]][t]-DS;
//		rep(i,1,top)cout<<s[i]<<" ";puts("");
	}
	rep(i,1,m)dis[x[i]][y[i]]=dis[y[i]][x[i]]=z[i];
	rep(i,1,n)dis[i][i]=0;
	rep(k,1,n)rep(i,1,n)rep(j,1,n)dis[i][j]=min(dis[i][k]+dis[k][j],dis[i][j]);
	rep(i,1,n){
		top=0;mx=0;
		rep(j,1,n){
			if(dis[i][j]>mx&&dis[i][j]!=inf)top=0,s[++top]=j,mx=dis[i][j];
			else if(dis[i][j]==mx)s[++top]=j;
		}
		rep(j,1,top)add(i,s[j],dis[i][s[j]]);
	}
	if(tmp!=1)q.push(t),vis[t]=1;
//	rep(i,1,_top)cout<<_s[i]<<" ";puts("");
//	cout<<DS+dis[_s[1]][t]<<endl;
//	rep(i,1,_top)q.push(_s[i]),vis[_s[i]]=1,ds[_s[i]]=-dis[_s[i]][t]-DS;
	while(!q.empty()){
		ll u=q.front();q.pop();vis[u]=0;
//		cout<<"IN"<<u<<endl;
		if(flag[u])continue;
		go(u){
			if(ds[v]>ds[u]-e[i].dis){
				ds[v]=ds[u]-e[i].dis;
				if(!vis[v]){
					cnt[v]++;q.push(v);vis[v]=1;
					if(cnt[v]>=n){puts("impossible");return 0;}
				}
			}
		}
	}
//	rep(i,1,n)cout<<flag[i]<<' ';puts("");
//	rep(i,1,n)cout<<ds[i]<<' ';puts("");
//	cout<<dis[8][1]<<endl;
	rep(i,1,n)ans=min(ans,ds[i]);
	writeln(tmp==1?-ans:-ans+dis[p][t]);
}
/*


*/

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 100
Accepted
time: 4ms
memory: 7656kb

input:

9 10 1 2
1 2 225869
2 3 1772
3 4 314393
4 5 692250
5 6 684107
4 6 532792
3 7 441133
7 8 468183
8 9 186297
7 9 228792

output:

impossible

result:

ok single line: 'impossible'

Test #2:

score: 0
Accepted
time: 1ms
memory: 7596kb

input:

9 10 3 2
1 2 225869
2 3 1772
3 4 314393
4 5 692250
5 6 684107
4 6 532792
3 7 441133
7 8 468183
8 9 186297
7 9 228792

output:

227641

result:

ok single line: '227641'

Test #3:

score: 0
Accepted
time: 1ms
memory: 7804kb

input:

8 22 8 1
1 2 11
1 3 11
1 4 11
1 5 11
1 6 11
1 7 10
2 3 12
2 4 12
2 5 12
2 6 12
2 7 11
3 4 13
3 5 13
3 6 13
3 7 12
4 5 14
4 6 14
4 7 13
5 6 15
5 7 14
6 7 15
7 8 1

output:

92

result:

ok single line: '92'

Test #4:

score: 0
Accepted
time: 3ms
memory: 7584kb

input:

6 7 3 6
1 3 2642
3 4 1253
2 4 64316
2 5 235162
6 5 2341
5 3 23
5 4 589201

output:

2364

result:

ok single line: '2364'

Test #5:

score: 0
Accepted
time: 2ms
memory: 5664kb

input:

4 4 3 2
1 2 1
2 3 10
2 4 5
4 3 6

output:

31

result:

ok single line: '31'

Test #6:

score: 0
Accepted
time: 3ms
memory: 7796kb

input:

2 1 2 1
2 1 1

output:

1

result:

ok single line: '1'

Test #7:

score: 0
Accepted
time: 2ms
memory: 9028kb

input:

300 44850 247 85
272 228 288849537
241 43 9873162
189 240 10538237
136 291 880425990
91 207 56502487
7 277 568371880
251 9 636070665
166 7 628732259
130 183 203171884
7 12 786299190
285 280 282670657
180 263 699873645
63 207 872780899
271 245 230237525
123 58 404988100
34 217 990722599
259 50 355842...

output:

impossible

result:

ok single line: 'impossible'

Test #8:

score: 0
Accepted
time: 3ms
memory: 5792kb

input:

3 2 1 2
2 3 12
1 2 70

output:

82

result:

ok single line: '82'

Test #9:

score: 0
Accepted
time: 2ms
memory: 7652kb

input:

3 3 1 3
1 3 1
2 3 1
1 2 1

output:

impossible

result:

ok single line: 'impossible'

Test #10:

score: 0
Accepted
time: 1ms
memory: 7804kb

input:

4 4 3 2
3 1 1
3 4 1
2 1 1
2 4 1

output:

impossible

result:

ok single line: 'impossible'

Test #11:

score: 0
Accepted
time: 3ms
memory: 5636kb

input:

4 4 2 1
3 1 5
1 4 3
2 1 5
2 4 5

output:

20

result:

ok single line: '20'

Test #12:

score: 0
Accepted
time: 4ms
memory: 7792kb

input:

4 4 2 4
3 4 7
4 2 5
1 2 5
3 2 5

output:

15

result:

ok single line: '15'

Test #13:

score: 0
Accepted
time: 3ms
memory: 5712kb

input:

4 4 2 3
2 1 10
1 4 9
4 2 2
1 3 3

output:

13

result:

ok single line: '13'

Test #14:

score: 0
Accepted
time: 0ms
memory: 7744kb

input:

4 4 3 4
3 2 9
4 2 13
1 2 20
1 4 16

output:

44

result:

ok single line: '44'

Test #15:

score: 0
Accepted
time: 3ms
memory: 7716kb

input:

4 4 4 2
4 3 368412026
4 2 248686681
1 3 856765094
3 2 319358821

output:

1424810596

result:

ok single line: '1424810596'

Test #16:

score: 0
Accepted
time: 0ms
memory: 7736kb

input:

4 5 3 2
3 1 3
4 2 7
4 3 17
2 3 14
2 1 4

output:

impossible

result:

ok single line: 'impossible'

Test #17:

score: 0
Accepted
time: 2ms
memory: 5544kb

input:

4 6 1 2
1 4 1
2 4 1
2 3 1
1 3 1
4 3 1
1 2 1

output:

impossible

result:

ok single line: 'impossible'

Test #18:

score: 0
Accepted
time: 4ms
memory: 7740kb

input:

5 5 4 5
1 5 1
3 5 1
2 1 2
3 4 2
2 4 2

output:

impossible

result:

ok single line: 'impossible'

Test #19:

score: 0
Accepted
time: 3ms
memory: 7752kb

input:

5 6 3 4
3 4 3
1 5 2
4 2 3
2 3 2
1 4 1
5 3 1

output:

impossible

result:

ok single line: 'impossible'

Test #20:

score: 0
Accepted
time: 1ms
memory: 5712kb

input:

5 6 3 2
1 5 10
3 1 8
3 5 6
3 4 7
1 4 6
1 2 6

output:

14

result:

ok single line: '14'

Test #21:

score: 0
Accepted
time: 3ms
memory: 5668kb

input:

5 7 5 1
1 2 1
4 2 1
2 5 1
4 3 1
1 4 1
1 5 1
1 3 1

output:

impossible

result:

ok single line: 'impossible'

Test #22:

score: 0
Accepted
time: 1ms
memory: 7628kb

input:

5 8 2 1
3 2 218
2 1 176
5 1 177
5 2 248
5 3 249
3 1 110
2 4 24
1 4 269

output:

impossible

result:

ok single line: 'impossible'

Test #23:

score: 0
Accepted
time: 3ms
memory: 7656kb

input:

6 6 2 6
4 5 34
4 2 13
6 4 18
3 6 3
1 2 15
1 6 2

output:

69

result:

ok single line: '69'

Test #24:

score: 0
Accepted
time: 2ms
memory: 7756kb

input:

6 7 2 4
6 1 5
2 4 3
3 5 5
5 4 2
4 3 1
6 2 5
6 3 6

output:

15

result:

ok single line: '15'

Test #25:

score: 0
Accepted
time: 3ms
memory: 5680kb

input:

6 8 3 5
3 5 5
4 1 6
5 2 9
5 1 10
1 6 1
3 2 10
4 6 1
2 6 6

output:

impossible

result:

ok single line: 'impossible'

Test #26:

score: 0
Accepted
time: 3ms
memory: 7624kb

input:

7 7 4 2
3 6 1
3 5 1
1 7 1
1 5 1
5 4 1
7 3 1
4 2 1

output:

1

result:

ok single line: '1'

Test #27:

score: 0
Accepted
time: 3ms
memory: 5716kb

input:

7 8 6 2
2 5 5
3 2 1
4 6 10
2 6 3
1 2 6
5 3 4
7 4 9
4 2 2

output:

14

result:

ok single line: '14'

Test #28:

score: 0
Accepted
time: 4ms
memory: 7724kb

input:

7 10 2 5
4 2 5
5 4 3
2 5 5
1 3 4
1 6 7
1 5 6
3 7 1
6 4 6
5 3 6
7 1 3

output:

impossible

result:

ok single line: 'impossible'

Test #29:

score: 0
Accepted
time: 3ms
memory: 7808kb

input:

7 10 5 2
3 6 39
7 2 38
1 3 5
2 3 38
4 2 8
1 4 26
5 6 9
2 6 12
7 5 10
5 2 20

output:

impossible

result:

ok single line: 'impossible'

Test #30:

score: 0
Accepted
time: 1ms
memory: 5624kb

input:

10 20 7 4
5 1 326
2 3 264
10 4 132
5 3 279
5 8 215
7 10 161
3 6 51
4 9 184
5 10 183
8 1 26
7 3 27
4 5 215
6 8 8
8 7 166
4 3 272
8 9 176
1 9 336
7 2 276
9 10 190
2 1 239

output:

impossible

result:

ok single line: 'impossible'

Test #31:

score: -100
Wrong Answer
time: 2ms
memory: 7788kb

input:

300 1000 172 215
188 170 616047457
52 84 278955639
40 242 753349504
163 138 601228798
161 16 632160688
179 229 448530394
69 143 427101036
289 245 202138801
196 67 997170084
39 117 521910244
280 119 344655702
79 105 274646714
241 183 674512683
113 66 937810400
273 93 112339663
3 233 976547617
250 290...

output:

impossible

result:

wrong answer 1st lines differ - expected: '5348814077', found: 'impossible'