QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#670360 | #3043. Lexicographically Minimum Walk | PNNNN | WA | 15ms | 11292kb | C++14 | 1.4kb | 2024-10-23 21:26:58 | 2024-10-23 21:27:01 |
Judging History
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 '