oj.uz

답안 #907396

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
907396 2024-01-15T13:27:57 Z RedSnow389 Commuter Pass (JOI18_commuter_pass) C++17
31 / 100
 383 ms 34244 KB 
#include <bits/stdc++.h>
using namespace std;
#define endl '\n'
#define ll long long
#define ld long double
#define fr(i,sz) for(i=0;i<sz;i++)
#define fa(i,v) for(auto &i:v)
#define yesno cout<<"YES"<<endl; else cout<<"NO"<<endl;
#define vvl vector<vector<ll> >       
#define vl vector<ll>  
#define pll pair<ll,ll>  
#define vpll vector<pair<ll,ll> > 
#define vvpll vector<vector<pair<ll,ll> > > 
#define mp make_pair
#define pb push_back
#define rs resize
#define cl(v) v.clear()
#define fastio ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
#define inf (ll)1e18
#define f1 first
#define f2 second
#define mod (ll)(1e9+7)
ll gcd(ll a, ll b) {if (b > a) {return gcd(b, a);} if (b == 0) {return a;} return gcd(b, a % b);}

int main(){
    fastio
    int t=1;
    // cin>>t;
    while(t--){
        ll n,m,s,t,u,w,i,ans1=inf,ans=inf;
        cin>>n>>m>>s>>t>>u>>w;
        vvpll v(n+1);
        vvl fromt(n+1), froms(n+1);
        while(m--){
            ll x,y,z;
            cin>>x>>y>>z;
            v[x].pb(mp(y,z));
            v[y].pb(mp(x,z));
        }
        vl distu(n+1,inf), distv(n+1,inf), dists(n+1,inf), distt(n+1,inf), newdists(n+1,inf), newdistt(n+1,inf);
        priority_queue<pll,vpll,greater<pll> > q;
        distu[u]=0;
        q.push(mp(0,u));
        while(!q.empty()){
            ll a=q.top().f2, b=q.top().f1;
            q.pop();
            if(distu[a]<b) continue;
            fa(i,v[a]) if(distu[i.f1]>b+i.f2){
                distu[i.f1]=b+i.f2;
                q.push(mp(distu[i.f1],i.f1));
            }
        }
        distv[w]=0;
        q.push(mp(0,w));
        while(!q.empty()){
            ll a=q.top().f2, b=q.top().f1;
            q.pop();
            if(distv[a]<b) continue;
            fa(i,v[a]) if(distv[i.f1]>b+i.f2){
                distv[i.f1]=b+i.f2;
                q.push(mp(distv[i.f1],i.f1));
            }
        }
        dists[s]=0;
        q.push(mp(0,s));
        vl vis(n+1,0);
        while(!q.empty()){
            ll a=q.top().f2, b=q.top().f1;
            q.pop();
            if(dists[a]<b) continue;
            fa(i,v[a]) if(dists[i.f1]>b+i.f2){
                fromt[i.f1].clear();
                fromt[i.f1].pb(a);
                dists[i.f1]=b+i.f2;
                q.push(mp(dists[i.f1],i.f1));
            }
            else if(dists[i.f1]==b+i.f2) fromt[i.f1].pb(a);
        }
        distt[t]=0;
        q.push(mp(0,t));
        while(!q.empty()){
            ll a=q.top().f2, b=q.top().f1;
            q.pop();
            if(distt[a]<b) continue;
            fa(i,v[a]) if(distt[i.f1]>b+i.f2){
                froms[i.f1].clear();
                froms[i.f1].pb(a);
                distt[i.f1]=b+i.f2;
                q.push(mp(distt[i.f1],i.f1));
            }
            else if(distt[i.f1]==b+i.f2) froms[i.f1].pb(a);
        }
        queue<ll> q1;
        ans=distu[w];
        q1.push(s);
        newdists[s]=distu[s];
        ans=min(ans,distv[s]+distu[s]);
        while(!q1.empty()){
            ll a=q1.front();
            q1.pop();
            if(vis[a]) continue;
            vis[a]=1;
            fa(i,froms[a]){
                q1.push(i);
                newdists[i]=min(newdists[a],distu[i]);
                ans=min(ans,newdists[i]+distv[i]);
            }
        }
        q1.push(t);
        newdistt[t]=distu[t];
        vis.assign(n+1,0);
        ans=min(ans,distv[t]+distu[t]);
        while(!q1.empty()){
            ll a=q1.front();
            q1.pop();
            if(vis[a]) continue;
            vis[a]=1;
            fa(i,fromt[a]){
                q1.push(i);
                newdistt[i]=min(newdistt[a],distu[i]);
                ans=min(ans,newdistt[i]+distv[i]);
            }
        }
        cout<<ans;
        // fr(i,n) cout<<distu[i+1]<<' ';
        // fr(i,n) cout<<distv[i+1]<<' ';
    }   
}

Compilation message

commuter_pass.cpp: In function 'int main()':
commuter_pass.cpp:30:24: warning: unused variable 'i' [-Wunused-variable]
   30 |         ll n,m,s,t,u,w,i,ans1=inf,ans=inf;
      |                        ^
commuter_pass.cpp:30:26: warning: unused variable 'ans1' [-Wunused-variable]
   30 |         ll n,m,s,t,u,w,i,ans1=inf,ans=inf;
      |                          ^~~~

Subtask #1
16.0 / 16.0

# 결과 실행 시간 메모리 Grader output
1 Correct 307 ms 31068 KB Output is correct
2 Correct 347 ms 29800 KB Output is correct
3 Correct 309 ms 34244 KB Output is correct
4 Correct 303 ms 33988 KB Output is correct
5 Correct 338 ms 33376 KB Output is correct
6 Correct 307 ms 33788 KB Output is correct
7 Correct 365 ms 33364 KB Output is correct
8 Correct 371 ms 33760 KB Output is correct
9 Correct 301 ms 34008 KB Output is correct
10 Correct 286 ms 34172 KB Output is correct
11 Correct 111 ms 26196 KB Output is correct
12 Correct 332 ms 33988 KB Output is correct

Subtask #2
15.0 / 15.0

# 결과 실행 시간 메모리 Grader output
1 Correct 334 ms 30012 KB Output is correct
2 Correct 375 ms 29684 KB Output is correct
3 Correct 383 ms 29756 KB Output is correct
4 Correct 343 ms 29716 KB Output is correct
5 Correct 362 ms 29792 KB Output is correct
6 Correct 359 ms 29876 KB Output is correct
7 Correct 360 ms 29584 KB Output is correct
8 Correct 352 ms 29568 KB Output is correct
9 Correct 338 ms 29720 KB Output is correct
10 Correct 330 ms 29756 KB Output is correct
11 Correct 154 ms 24112 KB Output is correct
12 Correct 321 ms 29796 KB Output is correct

Subtask #3
0 / 24.0

# 결과 실행 시간 메모리 Grader output
1 Correct 7 ms 2396 KB Output is correct
2 Correct 1 ms 348 KB Output is correct
3 Correct 1 ms 348 KB Output is correct
4 Correct 12 ms 4184 KB Output is correct
5 Correct 6 ms 2140 KB Output is correct
6 Correct 1 ms 604 KB Output is correct
7 Incorrect 1 ms 604 KB Output isn't correct
8 Halted 0 ms 0 KB -

Subtask #4
0 / 45.0

# 결과 실행 시간 메모리 Grader output
1 Correct 307 ms 31068 KB Output is correct
2 Correct 347 ms 29800 KB Output is correct
3 Correct 309 ms 34244 KB Output is correct
4 Correct 303 ms 33988 KB Output is correct
5 Correct 338 ms 33376 KB Output is correct
6 Correct 307 ms 33788 KB Output is correct
7 Correct 365 ms 33364 KB Output is correct
8 Correct 371 ms 33760 KB Output is correct
9 Correct 301 ms 34008 KB Output is correct
10 Correct 286 ms 34172 KB Output is correct
11 Correct 111 ms 26196 KB Output is correct
12 Correct 332 ms 33988 KB Output is correct
13 Correct 334 ms 30012 KB Output is correct
14 Correct 375 ms 29684 KB Output is correct
15 Correct 383 ms 29756 KB Output is correct
16 Correct 343 ms 29716 KB Output is correct
17 Correct 362 ms 29792 KB Output is correct
18 Correct 359 ms 29876 KB Output is correct
19 Correct 360 ms 29584 KB Output is correct
20 Correct 352 ms 29568 KB Output is correct
21 Correct 338 ms 29720 KB Output is correct
22 Correct 330 ms 29756 KB Output is correct
23 Correct 154 ms 24112 KB Output is correct
24 Correct 321 ms 29796 KB Output is correct
25 Correct 7 ms 2396 KB Output is correct
26 Correct 1 ms 348 KB Output is correct
27 Correct 1 ms 348 KB Output is correct
28 Correct 12 ms 4184 KB Output is correct
29 Correct 6 ms 2140 KB Output is correct
30 Correct 1 ms 604 KB Output is correct
31 Incorrect 1 ms 604 KB Output isn't correct
32 Halted 0 ms 0 KB -