Submission #66739

#	Time	Username	Problem	Language	Result	Execution time	Memory
66739		yusufake	Commuter Pass (JOI18_commuter_pass)	C++98	100 / 100	908 ms	196692 KiB

commuter_pass

#include<bits/stdc++.h> 
using namespace std; 

#define mp make_pair 
#define pb push_back 
#define st first 
#define nd second 

typedef long long ll; 
typedef pair < int , int > pp; 
const int mod = 1e9 + 7; 
const int N   = 5e5 + 5; 

priority_queue < pair < ll , pp > > Q;
vector < pp > V[N];
vector < int > Y[N],Z[N];
ll D[N][3],H[N][3],T[N],TT[N],M[N],MM[N],n,m,i,x,y,z,a,b,c,d,ans;


void f(int x, int h){
    while(Q.size()) Q.pop();
    ll p,u;
    Q.push(mp(0,mp(x,0)));
    for(; Q.size() ;){
        x = Q.top().nd.st;
        p = Q.top().nd.nd;
        u = Q.top().st;
        Q.pop();
        if(H[x][h]){
            if(!h && D[x][h] == -u){
                Y[p].pb(x);
                Z[x].pb(p);
            }
            continue;
        }
        H[x][h] = 1;
        D[x][h] = -u;
        if(!h) Y[p].pb(x);
        if(!h) Z[x].pb(p);
        for(auto t : V[x]){
            Q.push(mp(u-t.nd,mp(t.st,x)));
        }
    }
}

void g(int x){
    T[x] = 1;
    for(auto y : Z[x])
        if(!T[y])
            g(y);
}
void gg(int x){
    TT[x] = 1;
    M[x] = D[x][1];
    MM[x] = D[x][2];
    for(auto y : Y[x]){
        if(!T[y]) continue;
        if(!TT[y]) gg(y);
        M[x] = min(M[x] , M[y]);
        MM[x] = min(MM[x] , MM[y]);
    }
    //cout << x << " ss\n";
    ans = min(ans , D[x][2] + M[x]);
    ans = min(ans , D[x][1] + MM[x]);
}

int main(){
    scanf("%d%d",&n,&m);
    scanf("%d%d",&a,&b);
    scanf("%d%d",&c,&d);
    for(i=1;i<=m;i++){
        scanf("%d%d%d",&x,&y,&z);
        V[x].pb(mp(y,z)); V[y].pb(mp(x,z));
    }
    
    memset(D , 22 , sizeof D);
    f(a,0);
    f(c,1);
    f(d,2);
    //cout << b << " " << Z[b].size() << " aa\n";  
    g(b);
    //for(i=1;i<=n;i++) printf("%d ",T[i]); puts("");
    ans = D[d][1];
    gg(a);
    printf("%lld",ans);
    return 0;
}

Compilation message (stderr)

commuter_pass.cpp: In function 'int main()':
commuter_pass.cpp:68:23: warning: format '%d' expects argument of type 'int*', but argument 2 has type 'll* {aka long long int*}' [-Wformat=]
     scanf("%d%d",&n,&m);
                  ~~   ^
commuter_pass.cpp:68:23: warning: format '%d' expects argument of type 'int*', but argument 3 has type 'll* {aka long long int*}' [-Wformat=]
commuter_pass.cpp:69:23: warning: format '%d' expects argument of type 'int*', but argument 2 has type 'll* {aka long long int*}' [-Wformat=]
     scanf("%d%d",&a,&b);
                  ~~   ^
commuter_pass.cpp:69:23: warning: format '%d' expects argument of type 'int*', but argument 3 has type 'll* {aka long long int*}' [-Wformat=]
commuter_pass.cpp:70:23: warning: format '%d' expects argument of type 'int*', but argument 2 has type 'll* {aka long long int*}' [-Wformat=]
     scanf("%d%d",&c,&d);
                  ~~   ^
commuter_pass.cpp:70:23: warning: format '%d' expects argument of type 'int*', but argument 3 has type 'll* {aka long long int*}' [-Wformat=]
commuter_pass.cpp:72:32: warning: format '%d' expects argument of type 'int*', but argument 2 has type 'll* {aka long long int*}' [-Wformat=]
         scanf("%d%d%d",&x,&y,&z);
                        ~~      ^
commuter_pass.cpp:72:32: warning: format '%d' expects argument of type 'int*', but argument 3 has type 'll* {aka long long int*}' [-Wformat=]
commuter_pass.cpp:72:32: warning: format '%d' expects argument of type 'int*', but argument 4 has type 'll* {aka long long int*}' [-Wformat=]
commuter_pass.cpp:68:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%d%d",&n,&m);
     ~~~~~^~~~~~~~~~~~~~
commuter_pass.cpp:69:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%d%d",&a,&b);
     ~~~~~^~~~~~~~~~~~~~
commuter_pass.cpp:70:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%d%d",&c,&d);
     ~~~~~^~~~~~~~~~~~~~
commuter_pass.cpp:72:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         scanf("%d%d%d",&x,&y,&z);
         ~~~~~^~~~~~~~~~~~~~~~~~~

• Subtask 1: 16 / 16
• Subtask 2: 15 / 15
• Subtask 3: 24 / 24
• Subtask 4: 45 / 45