Submission #82492

#	Time	Username	Problem	Language	Result	Execution time	Memory
82492		hatuank97lhp	Commuter Pass (JOI18_commuter_pass)	C++14	31 / 100	782 ms	25880 KiB

commuter_pass

#include <bits/stdc++.h>
#define LL long long
#define F first
#define S second
#define mp make_pair

using namespace std;

void load() {
    #ifndef ONLINE_JUDGE
    freopen(".inp","r",stdin);
    freopen(".out","w",stdout);
    #endif // ONLINE_JUDGE
}
LL n,m,a,b,c,d;
const LL N = 1e5 + 123;
typedef pair < LL , LL > II;
vector < II > ed[N];
typedef pair < LL , II > IIII;
LL dp[3][N],f[N][2],ans ;

void dij(LL s, LL cs) {
    for (LL i = 1 ; i <= n ; ++ i)
        dp[cs][i] = 1e18;
    dp[cs][s] = 0;
    priority_queue < II , vector  < II > , greater < II > >  q;
    q.push(mp(0,s));
    while (!q.empty()) {
        II b = q.top();
        q.pop();
        if (b.F > dp[cs][b.S]) continue;
        for (II tmp : ed[b.S]) {
            LL v = tmp.F, w = tmp.S;
            if (dp[cs][v] > b.F + w)
                dp[cs][v] = b.F + w,
                q.push(mp(dp[cs][v],v));
        }
    }

}

void dij_2(LL s) {
    for (LL i = 1 ; i <= n ; ++ i)
        f[i][0] = f[i][1] = 1e18;
    f[s][0] = 0;
    if (dp[1][s] + dp[2][s] == dp[2][a])
        f[s][1] = 0;



    priority_queue < IIII , vector  <IIII>, greater < IIII > > q;
    q.push(mp(f[s][0],mp(s,0)));
    q.push(mp(f[s][1],mp(s,1)));

    while (!q.empty()) {
        IIII b = q.top();
        q.pop();
        if (f[b.S.F][b.S.S] < b.F) continue;
        for (II tmp : ed[b.S.F]) {
            LL v = tmp.F, w = tmp.S, typ = b.S.S;

            if (typ == 0) {
                if (f[v][0] > b.F + w)
                    f[v][0] = b.F + w,
                    q.push(mp(f[v][0], mp(v,0)));
                if (dp[1][v] + dp[2][v] == dp[2][a] && f[v][1] > b.F + w)
                    f[v][1] = b.F + w,
                    q.push(mp(f[v][1], mp(v,1)));
            }

            if (typ == 1) {
                if (f[v][0] > b.F + w)
                    f[v][0] = b.F + w,
                    q.push(mp(f[v][0], mp(v,0)));
                LL u = b.S.F;
                if (dp[1][u] + dp[2][v] + w == dp[2][a] && f[v][1] > b.F)
                    f[v][1] = b.F,
                    q.push(mp(f[v][1],mp(v,1)));
            }
        }
    }

    ans = min(ans,min(f[d][0],f[d][1]));
    return ;
}

void trungtt() {

    scanf("%lld%lld%lld%lld%lld%lld",&n,&m,&a,&b,&c,&d);
    for (LL i = 1 ; i <= m ; ++ i) {
        LL u,v,val;
        scanf("%lld%lld%lld",&u,&v,&val);
        ed[u].push_back(mp(v,val));
        ed[v].push_back(mp(u,val));
    }

    ans = 1e18;

    dij(a,1);
    dij(b,2);
    dij_2(c);
    swap(a,b);
    dij(a,1);
    dij(b,2);
    dij_2(c);
    printf("%lld",ans);
}

int main() {
   // load();
    trungtt();
    return 0;
}

Compilation message (stderr)

commuter_pass.cpp: In function 'void load()':
commuter_pass.cpp:11:12: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)', declared with attribute warn_unused_result [-Wunused-result]
     freopen(".inp","r",stdin);
     ~~~~~~~^~~~~~~~~~~~~~~~~~
commuter_pass.cpp:12:12: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)', declared with attribute warn_unused_result [-Wunused-result]
     freopen(".out","w",stdout);
     ~~~~~~~^~~~~~~~~~~~~~~~~~~
commuter_pass.cpp: In function 'void trungtt()':
commuter_pass.cpp:89:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%lld%lld%lld%lld%lld%lld",&n,&m,&a,&b,&c,&d);
     ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
commuter_pass.cpp:92:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         scanf("%lld%lld%lld",&u,&v,&val);
         ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~

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