QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#19865#2289. Jail or JoyrideXiao_Luo_XuanWA 45ms4880kbC++172.2kb2022-02-12 15:58:592022-05-06 07:22:48

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-06 07:22:48]
  • 评测
  • 测评结果:WA
  • 用时:45ms
  • 内存:4880kb
  • [2022-02-12 15:58:59]
  • 提交

answer

#include<bits/stdc++.h>
using namespace std;
const int N=330,M=1e5+5,INF=1e9;
int n,m,p,t,ans;
int dis[N][N],in[N],diss[N][N];
int F[N][N],G[N][N];

int Dis[N],num[N];
bool Vis[N];
queue <int> q;


bool vis[N];

void floyd(int dis[N][N]){
	for(int k=1;k<=n;k++)
		for(int u=1;u<=n;u++)
			for(int v=1;v<=n;v++)
				dis[u][v]=min(dis[u][v],dis[u][k]+dis[k][v]);
}

void dfs(int u,int ban){
	if(u==ban || vis[u]) return ;
	vis[u]=1;
	for(int v=1;v<=n;v++){
		if(u==v || F[u][v]==INF) continue;
		dfs(v,ban);
	}
}

void pr(int f[N][N]){
	cout<<"pr: "<<endl;
	for(int i=1;i<=n;i++){
		for(int j=1;j<=n;j++)
			cout<<f[i][j]<<" ";
		cout<<endl;
	}
	cout<<endl;
}

int main(){
	cin>>n>>m>>p>>t;
	for(int i=1;i<=n;i++)
		for(int j=1;j<=n;j++)
			dis[i][j]=F[i][j]=G[i][j]=INF;
	for(int i=1;i<=n;i++) dis[i][i]=F[i][i]=G[i][i]=0;
	
	for(int i=1;i<=m;i++){
		int u,v,w;
		cin>>u>>v>>w;
		in[u]++,in[v]++;
		dis[u][v]=min(G[u][v],w);
		dis[v][u]=min(G[v][u],w);
	}
	for(int i=1;i<=n;i++)
		for(int j=1;j<=n;j++)
			F[i][j]=dis[i][j];
	
	floyd(dis);
	dfs(p,t);
//	pr(dis);
	int tot=0,sav;
	for(int v=1;v<=n;v++){
		if(v==t || F[t][v]==INF) continue;
		if(vis[v]) tot++,sav=v;
	}
	
	for(int i=1;i<=n;i++) Dis[i]=-INF;
	if(tot==1){
		for(int i=1;i<=n;i++)
			for(int j=1;j<=n;j++)
				diss[i][j]=F[i][j];
		diss[sav][t]=diss[t][sav]=INF;
//		pr(diss);
		floyd(diss);
		int mx=0;
		for(int i=1;i<=n;i++) if(diss[t][i]<INF) mx=max(mx,diss[t][i]);
		for(int i=1;i<=n;i++)
			if(mx==diss[t][i]) Dis[i]=dis[t][i],q.push(i),Vis[i]=1;
	}
	else Dis[t]=0,q.push(t),Vis[t]=1;
	
	for(int u=1;u<=n;u++){
		int mx=0;
		for(int i=1;i<=n;i++) if(dis[u][i]<INF) mx=max(mx,dis[u][i]);
		for(int i=1;i<=n;i++) if(mx==dis[u][i]) G[u][i]=dis[u][i];
	}
//	pr(G);
	
	while(q.size()){
		int u=q.front();
		q.pop();
		Vis[u]=0;
		if(in[u]==1) continue;
		for(int v=1;v<=n;v++){
			if(u==v || G[u][v]==INF) continue;
			Dis[v]=max(Dis[v],Dis[u]+G[u][v]);
			if(!Vis[v]){
				q.push(v),Vis[v]=1;
				num[v]++;
				if(num[v]>n) return puts("impossible"),0;
			}
		}
	}
	
	for(int i=1;i<=n;i++){
		if(in[i]==1){
			ans=max(ans,dis[p][t]+Dis[i]);
		}
	}
	cout<<ans;
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 100
Accepted
time: 3ms
memory: 3760kb

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: 3ms
memory: 3620kb

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: 3ms
memory: 3664kb

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: 3608kb

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: 3ms
memory: 3736kb

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: 3660kb

input:

2 1 2 1
2 1 1

output:

1

result:

ok single line: '1'

Test #7:

score: 0
Accepted
time: 45ms
memory: 4876kb

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: 3632kb

input:

3 2 1 2
2 3 12
1 2 70

output:

82

result:

ok single line: '82'

Test #9:

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

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: 2ms
memory: 3596kb

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: 0ms
memory: 3672kb

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: 2ms
memory: 3640kb

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: 3596kb

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: 3724kb

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: 3736kb

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: 1ms
memory: 3520kb

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: 3ms
memory: 3584kb

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: 0ms
memory: 3588kb

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: 2ms
memory: 3672kb

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: 0ms
memory: 3540kb

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: 2ms
memory: 3732kb

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: 2ms
memory: 3736kb

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: 1ms
memory: 3736kb

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: 3ms
memory: 3600kb

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: 2ms
memory: 3680kb

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: 1ms
memory: 3536kb

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: 2ms
memory: 3568kb

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: 0ms
memory: 3600kb

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: 2ms
memory: 3688kb

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: 0ms
memory: 3752kb

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: 19ms
memory: 4880kb

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'