QOJ.ac

QOJ

ID	Problem	Submitter	Result	Time	Memory	Language	File size	Submit time	Judge time
#585626	#9260. Raiffeisenbank Logistics	ucup-team3474^#	TL	1242ms	3864kb	C++20	2.4kb	2024-09-23 21:32:53	2024-09-23 21:32:54

Judging History

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

[2024-09-23 21:32:54]
评测

测评结果：TL
用时：1242ms
内存：3864kb

查看

[2024-09-23 21:32:53]
提交

answer

#include<bits/stdc++.h>
using namespace std;
const int N=5e5+10,mod=998244353;
typedef long long ll;
typedef pair<ll,ll> PII;
ll n,m,k;
ll a[N],b[N];
char s[N];

typedef struct{
    int to,val,w;
}Node;

vector<Node> e[N];
int q[N];

vector<int> ee[N];

vector<int> mp[N];
vector<int> tf[N];

void __(){
    cin>>n>>m;
    for(int i=1;i<=n;i++) e[i].clear(),mp[i].clear(),ee[i].clear(),tf[i].clear();
    // mp.clear();
    deque<array<int,3>> q;
    for(int i=1;i<=m;i++){
        int u,v,w;
        cin>>u>>v>>w;
        e[u].push_back({v,w,0});
        e[v].push_back({u,w,1});
        ee[u].push_back(w);
        ee[v].push_back(w);
    }
    ee[1].push_back(-1);
    for(int i=1;i<=n;i++){
        sort(ee[i].begin(),ee[i].end());
        ee[i].erase(unique(ee[i].begin(),ee[i].end()),ee[i].end());
    }
    for(int i=1;i<=n;i++){
        for(int j=1;j<=e[i].size();j++) mp[i].push_back(1e9),tf[i].push_back(0);
    }
    mp[1][0]=0;
    tf[1][0]=1;
    q.push_back({1,-1,0});
    while(q.size()){
        auto t=q.front();
        q.pop_front();
        int ts=lower_bound(ee[t[0]].begin(),ee[t[0]].end(),t[1])-ee[t[0]].begin();
        // cout<<t[0]<<" "<<t
        // cout<<t[0]<<" "<<t[1]<<" "<<t[2]<<endl;
        for(auto [to,val,w]:e[t[0]]){
            if(val<=t[1]) continue;
            if(w==0){
               array<int,3> tt={to,val,w};
                int tts=lower_bound(ee[tt[0]].begin(),ee[tt[0]].end(),tt[1])-ee[tt[0]].begin();
                // if(mp.count(tt)) continue;
                if(mp[tt[0]][tts]>t[2]){
                mp[tt[0]][tts]=t[2];
                tf[tt[0]][tts]=1;
                tt[2]=t[2];
                q.push_front(tt);
                }
            }else{
               array<int,3> tt={to,val,w};
               int tts=lower_bound(ee[tt[0]].begin(),ee[tt[0]].end(),tt[1])-ee[tt[0]].begin();
                if(mp[tt[0]][tts]>t[2]+1){
                mp[tt[0]][tts]=t[2]+1;
                tf[tt[0]][tts]=1;
                tt[2]=t[2]+1;
                q.push_front(tt);
                }
            }
        }
    }
    int ans=1e9+8;
    for(auto v:mp[n]){
        ans=min(v,ans);
    }
    if(ans>1e8) cout<<-1<<"\n";
    else cout<<ans<<"\n";

}


int main(){
    ios::sync_with_stdio(0);
    cin.tie(0);
    int _;
    cin>>_;
    while(_--){
        __();
    }
}

Source code, Language: C++20

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 100

Accepted

time: 2ms

memory: 3844kb

input:

output:

result:

ok 1 number(s): "2"

Test #2:

score: 0

Accepted

time: 2ms

memory: 3840kb

input:

output:

-1
1

result:

ok 2 number(s): "-1 1"

Test #3:

score: 0

Accepted

time: 2ms

memory: 3628kb

input:

8
2 1
1 2 1
2 1
2 1 1
2 1
1 1 1
2 1
2 2 1
2 1
1 2 1000000000
2 1
2 1 1000000000
2 1
1 1 1000000000
2 1
2 2 1000000000

output:

0
1
-1
-1
0
1
-1
-1

result:

ok 8 numbers

Test #4:

score: 0

Accepted

time: 2ms

memory: 3840kb

input:

1
2 1
1 2 1

output:

result:

ok 1 number(s): "0"

Test #5:

score: 0

Accepted

time: 0ms

memory: 3648kb

input:

output:

-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
0
-1
-1
-1
1
-1
-1
-1
-1
-1
1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
0
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
0
-1
-1
-1
0
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
0
-1
-1
-1
-1
-1
-1
0
1
-1
-1
-1
-1
-1
-1
0
-1
-1
-1
-1
-1
1
-1
-1
0
-1
1
-1
-1
-...

result:

ok 1000 numbers

Test #6:

score: 0

Accepted

time: 4ms

memory: 3584kb

input:

output:

-1
-1
1
-1
1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
1
-1
1
-1
-1
-1
1
-1
0
0
-1
-1
-1
-1
1
1
-1
-1
-1
1
1
-1
-1
-1
-1
1
-1
1
-1
-1
-1
-1
-1
-1
-1
-1
-1
1
-1
1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
0
-1
0
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
0
-1
-1
0
-1
-1
1
0
0
1
-1
-1
-1
-1
1
-1
-1
-1
-1
...

result:

ok 1000 numbers

Test #7:

score: 0

Accepted

time: 0ms

memory: 3864kb

input:

output:

0
1
-1
2
-1
-1
1
0
0
-1
1
-1
0
-1
1
-1
-1
-1
-1
1
-1
-1
-1
2
-1
-1
-1
-1
-1
1
1
2
-1
1
-1
-1
2
1
-1
-1
-1
1
-1
1
-1
-1
-1
0
-1
-1
-1
-1
0
-1
0
1
1
-1
1
-1
-1
1
2
-1
-1
1
-1
-1
0
-1
0
-1
0
-1
-1
-1
-1
1
-1
0
-1
0
-1
1
0
0
-1
-1
-1
-1
-1
1
1
-1
2
-1
-1
0
-1
-1
-1
-1
1
-1
-1
-1
-1
-1
0
-1
1
-1
0
-1
0
-...

result:

ok 1000 numbers

Test #8:

score: 0

Accepted

time: 4ms

memory: 3564kb

input:

output:

2
-1
-1
-1
-1
-1
1
1
-1
-1
-1
-1
-1
2
-1
-1
-1
-1
-1
1
2
-1
0
-1
-1
-1
-1
0
2
-1
-1
-1
-1
-1
-1
1
-1
-1
-1
-1
1
-1
-1
1
-1
-1
-1
-1
-1
-1
-1
-1
-1
0
-1
-1
-1
-1
-1
0
-1
0
-1
-1
-1
-1
0
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
0
-1
-1
-1
0
2
-1
-1
-1
3
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
0
-1
-1
...

result:

ok 1000 numbers

Test #9:

score: 0

Accepted

time: 0ms

memory: 3584kb

input:

output:

1
-1
-1
-1
0
-1
-1
0
-1
-1
-1
-1
-1
-1
-1
-1
1
0
-1
-1
-1
-1
2
0
0
-1
1
-1
-1
-1
0
-1
3
-1
-1
1
0
-1
-1
-1
-1
0
-1
-1
-1
1
-1
-1
-1
-1
-1
-1
-1
-1
-1
1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
1
0
-1
-1
-1
-1
-1
1
0
-1
-1
-1
-1
-1
1
1
-1
-1
-1
1
0
-1
2
0
-1
-1
-1
-1
0
0
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
0
-1
0
-1
...

result:

ok 1000 numbers

Test #10:

score: 0

Accepted

time: 4ms

memory: 3820kb

input:

1000
10 10
10 10 268155137
5 10 540061009
1 10 110627680
1 4 533692575
3 5 10438095
6 7 730490278
6 2 985939776
8 10 500039201
1 9 185735931
4 2 729538420
10 10
8 1 326383784
5 3 726281100
4 6 279162422
4 4 243297959
1 2 984988531
3 10 856724546
2 4 627158366
4 5 880246199
9 1 675003875
7 7 76366643...

output:

0
-1
-1
-1
-1
0
-1
2
1
-1
2
-1
-1
-1
-1
1
-1
1
-1
0
-1
2
1
2
-1
-1
0
-1
1
-1
-1
1
-1
-1
-1
-1
-1
-1
0
0
-1
-1
-1
-1
-1
1
-1
1
-1
-1
1
-1
0
-1
-1
-1
-1
-1
1
1
1
-1
0
-1
-1
1
-1
-1
-1
-1
-1
-1
1
-1
-1
1
0
-1
-1
-1
0
1
-1
2
-1
2
-1
-1
-1
-1
-1
-1
-1
-1
1
-1
-1
1
-1
-1
-1
-1
1
-1
-1
-1
-1
-1
1
0
-1
0
-1...

result:

ok 1000 numbers

Test #11:

score: 0

Accepted

time: 4ms

memory: 3640kb

input:

output:

-1
1
-1
0
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
1
0
-1
-1
-1
-1
-1
-1
0
1
-1
-1
-1
-1
-1
0
1
-1
0
-1
-1
-1
-1
0
0
1
1
-1
1
-1
-1
-1
0
-1
0
-1
-1
-1
1
-1
-1
1
-1
-1
1
0
-1
-1
0
0
-1
-1
-1
0
-1
-1
-1
-1
-1
1
-1
-1
-1
1
1
1
0
-1
-1
-1
-1
-1
1
1
-1
1
-1
-1
-1
0
1
1
0
-1
-1
-1
-1
-1
0
0
-1
-1
-1
-1
0
-1
0
...

result:

ok 1000 numbers

Test #12:

score: 0

Accepted

time: 5ms

memory: 3588kb

input:

output:

-1
-1
2
0
0
-1
-1
-1
1
1
-1
-1
-1
-1
-1
-1
0
-1
-1
2
-1
-1
-1
-1
1
-1
0
0
1
1
1
1
1
0
-1
-1
-1
-1
-1
-1
-1
-1
0
-1
1
-1
2
0
2
1
-1
-1
1
-1
-1
-1
-1
-1
1
0
-1
-1
-1
-1
0
1
-1
0
2
0
-1
0
-1
2
1
-1
0
-1
-1
2
-1
-1
-1
-1
2
-1
1
-1
-1
0
0
-1
0
0
2
-1
0
0
-1
0
-1
-1
-1
-1
-1
-1
-1
-1
1
-1
1
-1
-1
1
1
-1
1...

result:

ok 1000 numbers

Test #13:

score: 0

Accepted

time: 5ms

memory: 3656kb

input:

output:

-1
0
-1
0
0
-1
-1
-1
-1
-1
2
1
-1
-1
-1
-1
-1
0
-1
1
-1
-1
-1
0
-1
-1
-1
2
1
-1
-1
1
-1
-1
2
-1
0
1
1
-1
-1
-1
-1
-1
0
1
1
-1
-1
2
-1
-1
2
2
0
1
-1
0
-1
-1
0
1
-1
1
-1
0
-1
-1
0
1
2
0
0
-1
1
-1
1
0
-1
-1
-1
-1
0
0
-1
-1
0
2
1
0
1
-1
-1
2
1
1
0
0
2
2
1
1
-1
0
0
0
1
0
-1
1
-1
1
0
0
-1
-1
-1
-1
1
-1
-1...

result:

ok 1000 numbers

Test #14:

score: 0

Accepted

time: 5ms

memory: 3592kb

input:

output:

result:

ok 1000 numbers

Test #15:

score: 0

Accepted

time: 3ms

memory: 3584kb

input:

output:

result:

ok 1000 numbers

Test #16:

score: 0

Accepted

time: 6ms

memory: 3524kb

input:

1000
10 20
9 8 326353980
1 10 321178299
4 8 970616710
4 9 550923176
8 9 682488932
10 6 752852755
5 10 399703822
10 10 207683413
7 9 84451826
7 8 820433227
7 5 97884128
6 7 1405220
1 5 287655030
8 9 868446569
4 1 421832399
9 4 913601101
2 9 361785960
9 3 425625400
3 9 1891923
8 1 112588430
10 20
6 9 ...

output:

result:

ok 1000 numbers

Test #17:

score: 0

Accepted

time: 7ms

memory: 3584kb

input:

output:

result:

ok 1000 numbers

Test #18:

score: 0

Accepted

time: 10ms

memory: 3528kb

input:

output:

result:

ok 1000 numbers

Test #19:

score: 0

Accepted

time: 6ms

memory: 3524kb

input:

output:

result:

ok 1000 numbers

Test #20:

score: 0

Accepted

time: 14ms

memory: 3652kb

input:

output:

result:

ok 1000 numbers

Test #21:

score: 0

Accepted

time: 19ms

memory: 3680kb

input:

output:

result:

ok 1000 numbers

Test #22:

score: 0

Accepted

time: 18ms

memory: 3856kb

input:

1000
10 50
2 2 954153759
1 3 283444488
8 10 897162377
6 2 701352810
5 8 872948443
6 10 320895294
10 9 697730752
5 4 375661090
3 4 673334850
6 9 215515206
10 7 977251708
6 1 888046403
5 2 292147356
9 9 840382008
3 10 430429980
6 8 921004331
4 10 298467905
7 1 160104863
10 3 444341972
10 4 653051505
9...

output:

result:

ok 1000 numbers

Test #23:

score: 0

Accepted

time: 49ms

memory: 3724kb

input:

output:

result:

ok 1000 numbers

Test #24:

score: 0

Accepted

time: 66ms

memory: 3700kb

input:

output:

result:

ok 1000 numbers

Test #25:

score: 0

Accepted

time: 80ms

memory: 3592kb

input:

output:

result:

ok 1000 numbers

Test #26:

score: 0

Accepted

time: 201ms

memory: 3712kb

input:

output:

result:

ok 1000 numbers

Test #27:

score: 0

Accepted

time: 1242ms

memory: 3700kb

input:

output:

result:

ok 1000 numbers

Test #28:

score: -100

Time Limit Exceeded

input:

1000
10 500
8 9 67526824
5 4 559064935
10 5 4911091
10 1 665435421
10 9 676899734
7 1 937378183
8 5 573246092
4 7 989380774
4 6 200810178
7 1 416005093
8 8 742684190
1 10 268750539
2 5 718281171
1 8 934536165
1 5 814664163
2 7 237449715
2 1 203051765
6 7 306356562
10 3 428234841
3 1 760994730
10 2 7...

output: