QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#670360#3043. Lexicographically Minimum WalkPNNNNWA 15ms11292kbC++141.4kb2024-10-23 21:26:582024-10-23 21:27:01

Judging History

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

  • [2024-10-23 21:27:01]
  • 评测
  • 测评结果:WA
  • 用时:15ms
  • 内存:11292kb
  • [2024-10-23 21:26:58]
  • 提交

answer

#include<bits/stdc++.h>
#define int long long
#define fr first
#define sc second
#define lowbit(x) x&-x
using namespace std;

int n,m,S,T,flag;

struct line{
	int y,w;
};vector <line> to[100005];

inline bool cmp(line A,line B){
	return A.w<B.w;
}

int vis[100005];

pair<int,int> pre[100005];

inline void dfs(int x){
	vis[x]=1;
	for(int i=0;i<to[x].size();i++){
		int y=to[x][i].y,w=to[x][i].w;
		if(vis[y])continue;
		pre[y]={x,w},dfs(y);
	}return;
}

vector <int> ans;

inline void solve(){
	int cur=T;
	if(!pre[T].fr)return;
	while(cur!=S){
		if(cur!=T){
			for(auto nxt:to[cur]){
				if(nxt.y==pre[cur].fr&&nxt.w<ans.back()){
					flag=1;
				}
			}
		}
		ans.push_back(pre[cur].sc);
		cur=pre[cur].fr;
	}return;
}

inline int read(){
	register int x=0,t=0;
	static char ch=getchar();
	while(!isdigit(ch))t|=(ch=='-'),ch=getchar();
	while(isdigit(ch)){x=(x<<1)+(x<<3)+(ch^48);ch=getchar();}
	return t?-x:x;
}

signed main(){
	
	n=read(),m=read(),S=read(),T=read();
	for(int i=1;i<=m;i++){
		int x=read(),y=read(),w=read();
		to[x].push_back({y,w});
	}
	for(int i=1;i<=n;i++){
		sort(to[i].begin(),to[i].end(),cmp);
	}
	dfs(S),solve();
	
	if(!ans.size()){
		cout<<"IMPOSSIBLE";
		return 0;
	}
	if(flag){
		cout<<"TOO LONG";
		return 0;
	}
	for(int i=ans.size()-1;i>=0;i--){
		cout<<ans[i]<<' ';
	}
	
	return 0;
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 100
Accepted
time: 1ms
memory: 6928kb

input:

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

output:

1 7 

result:

ok single line: '1 7 '

Test #2:

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

input:

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

output:

TOO LONG

result:

ok single line: 'TOO LONG'

Test #3:

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

input:

2 0 2 1

output:

IMPOSSIBLE

result:

ok single line: 'IMPOSSIBLE'

Test #4:

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

input:

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

output:

3 1 5 

result:

ok single line: '3 1 5 '

Test #5:

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

input:

2 1 2 1
2 1 7

output:

7 

result:

ok single line: '7 '

Test #6:

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

input:

2 2 1 2
1 2 2
2 1 1

output:

2 

result:

ok single line: '2 '

Test #7:

score: 0
Accepted
time: 15ms
memory: 11292kb

input:

28859 86572 9295 11138
20786 10116 517787813
15575 14210 496341115
3830 4061 197006194
17520 5640 491762666
5140 21769 335255632
1656 6657 593849630
22703 267 432722157
24447 19519 787542727
19699 8688 505772317
1872 4189 209599628
12873 21023 303869213
16428 25691 369100452
24666 22655 490450477
69...

output:

276564833 747181428 245358434 243885332 117499601 619812353 284290651 299304374 902348522 88409440 269505876 35537697 270772809 386354731 507174655 86955126 25262475 233484277 978898295 176709567 234217699 53693224 853405827 538248861 841660562 239847518 347254527 81719421 326831893 336594724 242183...

result:

ok single line: '276564833 747181428 245358434 ... 105378754 437440589 546992718 '

Test #8:

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

input:

11 19 7 2
7 2 28748732
7 6 797829355
9 2 160449218
3 8 378994618
6 1 138996221
8 3 840594328
7 5 818008580
1 8 954291757
2 1 556259670
7 10 290688600
4 9 706926230
5 9 164163676
1 4 782177068
11 6 789301711
11 3 389872647
3 5 69356287
3 4 743988075
8 10 155374934
7 11 404011431

output:

28748732 

result:

ok single line: '28748732 '

Test #9:

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

input:

9 15 1 6
6 7 462224593
2 3 743144908
7 6 789301711
3 8 384836991
8 1 290688600
4 8 378994618
7 5 576823355
1 9 839296263
6 4 902236202
5 2 191890310
1 6 492601449
4 3 125660016
7 9 28748732
9 2 69356287
2 4 650287940

output:

492601449 

result:

ok single line: '492601449 '

Test #10:

score: -100
Wrong Answer
time: 1ms
memory: 7824kb

input:

100 157 54 89
89 73 293931814
63 14 209896431
5 30 191699654
66 70 392042756
96 61 941158190
99 58 444754263
27 55 71758606
19 15 731546581
88 5 700175183
99 2 179330504
51 77 35043830
6 31 116721425
77 39 948580482
16 36 226667776
61 89 131822429
12 26 476717409
4 46 885401404
66 72 861769143
12 3 ...

output:

867382649 760216468 636920039 815559762 273692416 563253880 273534992 863053870 407271866 290237604 392042756 220134761 336332701 401768215 91724204 501480826 805335815 640819451 228623399 189745056 240008060 731546581 184258241 55762240 35043830 948580482 20487725 29948938 510401935 254961810 71758...

result:

wrong answer 1st lines differ - expected: 'TOO LONG', found: '867382649 760216468 636920039 ... 449510794 941158190 131822429 '