QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#19864#2289. Jail or JoyrideAppleblue17#WA 46ms4824kbC++172.2kb2022-02-12 15:56:522022-05-06 07:22:44

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:44]
  • 评测
  • 测评结果:WA
  • 用时:46ms
  • 内存:4824kb
  • [2022-02-12 15:56:52]
  • 提交

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

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

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

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

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

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

input:

2 1 2 1
2 1 1

output:

1

result:

ok single line: '1'

Test #7:

score: 0
Accepted
time: 46ms
memory: 4824kb

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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'