제출 #82609

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
82609		hatuank97lhp	Commuter Pass (JOI18_commuter_pass)	C++14	100 / 100	915 ms	76052 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
}
int n,m,a,b,c,d;
const int N = 1e5 + 123;
typedef pair < LL , int > II;
vector < II > ed[N];
typedef pair < LL , II > IIII;
LL dp[3][N],f[N][4],ans ;

void dij(int s, int cs) {
    for (int 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]) {
            int 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(int s) {
    for (int i = 1 ; i <= n ; ++ i)
        for (int j = 0 ; j < 4 ; ++ j)
        f[i][j] = 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]) {
            int 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)));
                int u = b.S.F;
                if (dp[1][u] + dp[2][v] + w == dp[2][a] && f[v][2] > b.F)
                    f[v][2] = b.F,
                    q.push(mp(f[v][2],mp(v,2)));
            }

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

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

void trungtt() {

    scanf("%d%d%d%d%d%d",&n,&m,&a,&b,&c,&d);
    for (int i = 1 ; i <= m ; ++ i) {
        int u,v,val;
        scanf("%d%d%d",&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;
}

컴파일 시 표준 에러 (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:106:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%d%d%d%d%d%d",&n,&m,&a,&b,&c,&d);
     ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
commuter_pass.cpp:109:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         scanf("%d%d%d",&u,&v,&val);
         ~~~~~^~~~~~~~~~~~~~~~~~~~~

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