제출 #760604

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
760604		Fidisk	Commuter Pass (JOI18_commuter_pass)	C++14	0 / 100	9 ms	14496 KiB

commuter_pass

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

#define edge(xxxx,yyyy) ((xxxx)*(m+5)+(yyyy))
#define oo 1e18
#define fi first
#define se second
#define sp(iiii) setprecision(iiii)
#define IO ios_base::sync_with_stdio(false); cin.tie(0)
#define ms(aaaa,xxxx) memset(aaaa,xxxx,sizeof(aaaa))
#define cntbit(xxxx) __builtin_popcount(xxxx)
#define getbit(xxxx,aaaa) (((xxxx)>>((aaaa)-1))&1)
#define totbit(xxxx) (32-__builtin_clz(xxxx))
#define totbitll(xxxx) (64-__builtin_clzll(ll(xxxx)))

typedef long double ld;
typedef long long ll;
typedef unsigned long long ull;
typedef pair<int,int> pii;
typedef pair<pair<int,int>,int> piii;
typedef pair<long long,long long> pll;
typedef pair<pair<long long,long long>,long long> plll;
typedef pair<pair<long long,long long>,pair<long long,long long>> pllll;
typedef pair<pair<long long,long long>,bool> pllb;

const ll base=333333349;
const ll mod=1e9+7;
const ld eps=1e-5;
const ll maxn=50009;

struct comp{
    bool operator() (pll x,pll y) {
        return x.se>y.se;
    }
};

priority_queue<pll,vector<pll>,comp> heap;
ll dist[6][200009],n,m,s1,s2,t1,t2,i,res,u,v,w,antidistu[200009],distu[200009],distv[200009],antidistv[200009];
vector<pll> g[200009],antidag[200009],dag[200009];

void dijkstra(ll layer,ll source) {
    for (ll ii=1;ii<=n;ii++) {
        dist[layer][ii]=oo;
    }
    dist[layer][source]=0;
    heap.push({source,0});
    while (!heap.empty()) {
        ll x=heap.top().fi;
        ll y=heap.top().se;
        heap.pop();
        if (dist[layer][x]<y) continue;
        for (pll ii:g[x]) {
            if (dist[layer][ii.fi]>dist[layer][x]+ii.se) {
                dist[layer][ii.fi]=dist[layer][x]+ii.se;
                heap.push({ii.fi,dist[layer][ii.fi]});
            }
        }
    }
}

int main(){
    IO;
    #ifndef ONLINE_JUDGE
        freopen("test.inp", "r", stdin);
        freopen("test.out", "w", stdout);
    #else
    #endif
    cin>>n>>m;
    cin>>s1>>t1;
    cin>>s2>>t2;
    for (i=1;i<=m;i++) {
        cin>>u>>v>>w;
        g[u].push_back({v,w});
        g[v].push_back({u,w});
    }
    dijkstra(1,s1);
    dijkstra(2,t1);
    dijkstra(3,s2);
    dijkstra(4,t2);
    /*
    for (i=1;i<=n;i++) {
        cout<<dist[1][i]<<' ';
    }
    cout<<'\n';
    for (i=1;i<=n;i++) {
        cout<<dist[2][i]<<' ';
    }
    cout<<'\n';
    for (i=1;i<=n;i++) {
        cout<<dist[3][i]<<' ';
    }
    cout<<'\n';
    for (i=1;i<=n;i++) {
        cout<<dist[4][i]<<' ';
    }
    cout<<'\n';
    */
    for (i=1;i<=n;i++) {
        distu[i]=oo;
        distv[i]=oo;
        antidistu[i]=oo;
        antidistv[i]=oo;
    }
    for (i=1;i<=n;i++) {
        if (dist[1][i]+dist[2][i]!=dist[1][t1]) continue;
        for (pll ii:g[i]) {
            if (dist[1][i]+ii.se+dist[2][ii.fi]==dist[1][t1]) {
                dag[i].push_back({ii.fi,ii.se});
                antidag[ii.fi].push_back({i,ii.se});
                //cout<<"? "<<i<<' '<<ii.fi<<' '<<ii.se<<'\n';
            }
        }
    }
    for (i=1;i<=n;i++) {
        //distu[i]=oo;
        if (dist[1][i]+dist[2][i]!=dist[1][t1]) continue;
        distu[i]=dist[3][i];
        for (pll ii:antidag[i]) {
            distu[i]=min(distu[i],distu[ii.fi]);
        }
        for (pll ii:g[i]) {
            distu[i]=min(distu[i],distu[ii.fi]+ii.se);
        }
    }
    for (i=1;i<=n;i++) {
        //distv[i]=oo;
        if (dist[1][i]+dist[2][i]!=dist[1][t1]) continue;
        distv[i]=dist[4][i];
        for (pll ii:dag[i]) {
            distv[i]=min(distv[i],distv[ii.fi]);
        }
        for (pll ii:g[i]) {
            distv[i]=min(distv[i],distv[ii.fi]+ii.se);
        }
    }
    for (i=1;i<=n;i++) {
        //antidistu[i]=oo;
        if (dist[1][i]+dist[2][i]!=dist[1][t1]) continue;
        antidistu[i]=dist[3][i];
        for (pll ii:dag[i]) {
            antidistu[i]=min(antidistu[i],antidistu[ii.fi]);
        }
        for (pll ii:g[i]) {
            antidistu[i]=min(antidistu[i],antidistu[ii.fi]+ii.se);
        }
    }
    for (i=1;i<=n;i++) {
        //antidistv[i]=oo;
        if (dist[1][i]+dist[2][i]!=dist[1][t1]) continue;
        antidistv[i]=dist[4][i];
        for (pll ii:antidag[i]) {
            antidistv[i]=min(antidistv[i],antidistv[ii.fi]);
        }
        for (pll ii:g[i]) {
            antidistv[i]=min(antidistv[i],antidistv[ii.fi]+ii.se);
        }
    }
    for (i=1;i<=n;i++) {
        //distu[i]=oo;
        if (dist[1][i]+dist[2][i]!=dist[1][t1]) continue;
        distu[i]=dist[3][i];
        for (pll ii:antidag[i]) {
            distu[i]=min(distu[i],distu[ii.fi]);
        }
        for (pll ii:g[i]) {
            distu[i]=min(distu[i],distu[ii.fi]+ii.se);
        }
    }
    for (i=1;i<=n;i++) {
        //distv[i]=oo;
        if (dist[1][i]+dist[2][i]!=dist[1][t1]) continue;
        distv[i]=dist[4][i];
        for (pll ii:dag[i]) {
            distv[i]=min(distv[i],distv[ii.fi]);
        }
        for (pll ii:g[i]) {
            distv[i]=min(distv[i],distv[ii.fi]+ii.se);
        }
    }
    for (i=1;i<=n;i++) {
        //antidistu[i]=oo;
        if (dist[1][i]+dist[2][i]!=dist[1][t1]) continue;
        antidistu[i]=dist[3][i];
        for (pll ii:dag[i]) {
            antidistu[i]=min(antidistu[i],antidistu[ii.fi]);
        }
        for (pll ii:g[i]) {
            antidistu[i]=min(antidistu[i],antidistu[ii.fi]+ii.se);
        }
    }
    for (i=1;i<=n;i++) {
        //antidistv[i]=oo;
        if (dist[1][i]+dist[2][i]!=dist[1][t1]) continue;
        antidistv[i]=dist[4][i];
        for (pll ii:antidag[i]) {
            antidistv[i]=min(antidistv[i],antidistv[ii.fi]);
        }
        for (pll ii:g[i]) {
            antidistv[i]=min(antidistv[i],antidistv[ii.fi]+ii.se);
        }
    }
    for (i=1;i<=n;i++) {
        //distu[i]=oo;
        if (dist[1][i]+dist[2][i]!=dist[1][t1]) continue;
        distu[i]=dist[3][i];
        for (pll ii:antidag[i]) {
            distu[i]=min(distu[i],distu[ii.fi]);
        }
        for (pll ii:g[i]) {
            distu[i]=min(distu[i],distu[ii.fi]+ii.se);
        }
    }
    for (i=1;i<=n;i++) {
        //distv[i]=oo;
        if (dist[1][i]+dist[2][i]!=dist[1][t1]) continue;
        distv[i]=dist[4][i];
        for (pll ii:dag[i]) {
            distv[i]=min(distv[i],distv[ii.fi]);
        }
        for (pll ii:g[i]) {
            distv[i]=min(distv[i],distv[ii.fi]+ii.se);
        }
    }
    for (i=1;i<=n;i++) {
        //antidistu[i]=oo;
        if (dist[1][i]+dist[2][i]!=dist[1][t1]) continue;
        antidistu[i]=dist[3][i];
        for (pll ii:dag[i]) {
            antidistu[i]=min(antidistu[i],antidistu[ii.fi]);
        }
        for (pll ii:g[i]) {
            antidistu[i]=min(antidistu[i],antidistu[ii.fi]+ii.se);
        }
    }
    for (i=1;i<=n;i++) {
        //antidistv[i]=oo;
        if (dist[1][i]+dist[2][i]!=dist[1][t1]) continue;
        antidistv[i]=dist[4][i];
        for (pll ii:antidag[i]) {
            antidistv[i]=min(antidistv[i],antidistv[ii.fi]);
        }
        for (pll ii:g[i]) {
            antidistv[i]=min(antidistv[i],antidistv[ii.fi]+ii.se);
        }
    }
    for (i=1;i<=n;i++) {
        //distu[i]=oo;
        if (dist[1][i]+dist[2][i]!=dist[1][t1]) continue;
        distu[i]=dist[3][i];
        for (pll ii:antidag[i]) {
            distu[i]=min(distu[i],distu[ii.fi]);
        }
        for (pll ii:g[i]) {
            distu[i]=min(distu[i],distu[ii.fi]+ii.se);
        }
    }
    for (i=1;i<=n;i++) {
        //distv[i]=oo;
        if (dist[1][i]+dist[2][i]!=dist[1][t1]) continue;
        distv[i]=dist[4][i];
        for (pll ii:dag[i]) {
            distv[i]=min(distv[i],distv[ii.fi]);
        }
        for (pll ii:g[i]) {
            distv[i]=min(distv[i],distv[ii.fi]+ii.se);
        }
    }
    for (i=1;i<=n;i++) {
        //antidistu[i]=oo;
        if (dist[1][i]+dist[2][i]!=dist[1][t1]) continue;
        antidistu[i]=dist[3][i];
        for (pll ii:dag[i]) {
            antidistu[i]=min(antidistu[i],antidistu[ii.fi]);
        }
        for (pll ii:g[i]) {
            antidistu[i]=min(antidistu[i],antidistu[ii.fi]+ii.se);
        }
    }
    for (i=1;i<=n;i++) {
        //antidistv[i]=oo;
        if (dist[1][i]+dist[2][i]!=dist[1][t1]) continue;
        antidistv[i]=dist[4][i];
        for (pll ii:antidag[i]) {
            antidistv[i]=min(antidistv[i],antidistv[ii.fi]);
        }
        for (pll ii:g[i]) {
            antidistv[i]=min(antidistv[i],antidistv[ii.fi]+ii.se);
        }
    }
    for (i=1;i<=n;i++) {
        //distu[i]=oo;
        if (dist[1][i]+dist[2][i]!=dist[1][t1]) continue;
        distu[i]=dist[3][i];
        for (pll ii:antidag[i]) {
            distu[i]=min(distu[i],distu[ii.fi]);
        }
        for (pll ii:g[i]) {
            distu[i]=min(distu[i],distu[ii.fi]+ii.se);
        }
    }
    for (i=1;i<=n;i++) {
        //distv[i]=oo;
        if (dist[1][i]+dist[2][i]!=dist[1][t1]) continue;
        distv[i]=dist[4][i];
        for (pll ii:dag[i]) {
            distv[i]=min(distv[i],distv[ii.fi]);
        }
        for (pll ii:g[i]) {
            distv[i]=min(distv[i],distv[ii.fi]+ii.se);
        }
    }
    for (i=1;i<=n;i++) {
        //antidistu[i]=oo;
        if (dist[1][i]+dist[2][i]!=dist[1][t1]) continue;
        antidistu[i]=dist[3][i];
        for (pll ii:dag[i]) {
            antidistu[i]=min(antidistu[i],antidistu[ii.fi]);
        }
        for (pll ii:g[i]) {
            antidistu[i]=min(antidistu[i],antidistu[ii.fi]+ii.se);
        }
    }
    for (i=1;i<=n;i++) {
        //antidistv[i]=oo;
        if (dist[1][i]+dist[2][i]!=dist[1][t1]) continue;
        antidistv[i]=dist[4][i];
        for (pll ii:antidag[i]) {
            antidistv[i]=min(antidistv[i],antidistv[ii.fi]);
        }
        for (pll ii:g[i]) {
            antidistv[i]=min(antidistv[i],antidistv[ii.fi]+ii.se);
        }
    }
    for (i=1;i<=n;i++) {
        //distu[i]=oo;
        if (dist[1][i]+dist[2][i]!=dist[1][t1]) continue;
        distu[i]=dist[3][i];
        for (pll ii:antidag[i]) {
            distu[i]=min(distu[i],distu[ii.fi]);
        }
        for (pll ii:g[i]) {
            distu[i]=min(distu[i],distu[ii.fi]+ii.se);
        }
    }
    for (i=1;i<=n;i++) {
        //distv[i]=oo;
        if (dist[1][i]+dist[2][i]!=dist[1][t1]) continue;
        distv[i]=dist[4][i];
        for (pll ii:dag[i]) {
            distv[i]=min(distv[i],distv[ii.fi]);
        }
        for (pll ii:g[i]) {
            distv[i]=min(distv[i],distv[ii.fi]+ii.se);
        }
    }
    for (i=1;i<=n;i++) {
        //antidistu[i]=oo;
        if (dist[1][i]+dist[2][i]!=dist[1][t1]) continue;
        antidistu[i]=dist[3][i];
        for (pll ii:dag[i]) {
            antidistu[i]=min(antidistu[i],antidistu[ii.fi]);
        }
        for (pll ii:g[i]) {
            antidistu[i]=min(antidistu[i],antidistu[ii.fi]+ii.se);
        }
    }
    for (i=1;i<=n;i++) {
        //antidistv[i]=oo;
        if (dist[1][i]+dist[2][i]!=dist[1][t1]) continue;
        antidistv[i]=dist[4][i];
        for (pll ii:antidag[i]) {
            antidistv[i]=min(antidistv[i],antidistv[ii.fi]);
        }
        for (pll ii:g[i]) {
            antidistv[i]=min(antidistv[i],antidistv[ii.fi]+ii.se);
        }
    }
    res=dist[3][t2];
    /*
    for (i=1;i<=n;i++) {
        cout<<distu[i]<<' ';
    }
    cout<<'\n';
    for (i=1;i<=n;i++) {
        cout<<distv[i]<<' ';
    }
    cout<<'\n';
    for (i=1;i<=n;i++) {
        cout<<antidistu[i]<<' ';
    }
    cout<<'\n';
    for (i=1;i<=n;i++) {
        cout<<antidistv[i]<<' ';
    }
    cout<<'\n';
    */
    for (i=1;i<=n;i++) {
        res=min(res,dist[4][i]+min(distu[i],antidistu[i]));
        //cout<<"!"<<i<<' '<<res<<' '<<dist[4][i]<<' '<<distu[i]<<' '<<antidistu[i]<<' '<<dist[4][i]+min(distu[i],antidistu[i])<<'\n';
        res=min(res,dist[3][i]+min(distv[i],antidistv[i]));
        //cout<<"!"<<i<<' '<<res<<' '<<dist[3][i]<<' '<<distv[i]<<' '<<antidistv[i]<<' '<<dist[3][i]+min(distv[i],antidistv[i])<<'\n';
    }
    for (i=1;i<=n;i++) {
        res=min(res,min(distv[i],antidistv[i])+min(distu[i],antidistu[i]));
        //cout<<"!"<<i<<' '<<res<<' '<<dist[4][i]<<' '<<distu[i]<<' '<<antidistu[i]<<' '<<dist[4][i]+min(distu[i],antidistu[i])<<'\n';
        res=min(res,min(distu[i],antidistu[i])+min(distv[i],antidistv[i]));
        //cout<<"!"<<i<<' '<<res<<' '<<dist[3][i]<<' '<<distv[i]<<' '<<antidistv[i]<<' '<<dist[3][i]+min(distv[i],antidistv[i])<<'\n';
    }
    cout<<res<<'\n';
}

컴파일 시 표준 에러 (stderr) 메시지

commuter_pass.cpp: In function 'int main()':
commuter_pass.cpp:64:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   64 |         freopen("test.inp", "r", stdin);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
commuter_pass.cpp:65:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   65 |         freopen("test.out", "w", stdout);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~

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