Submission #1319030

#	Time	Username	Problem	Language	Result	Execution time	Memory
1319030		hanguyendanghuy	Commuter Pass (JOI18_commuter_pass)	C++20	15 / 100	1775 ms	327680 KiB

commuter_pass

//___  ___          _        _             _____             _
//|  \/  |         | |      | |           /  ___|           | |
//| .  . | __ _  __| | ___  | |__  _   _  \ `--.  __ _ _   _| |
//| |\/| |/ _` |/ _` |/ _ \ | '_ \| | | |  `--. \/ _` | | | | |
//| |  | | (_| | (_| |  __/ | |_) | |_| | /\__/ / (_| | |_| | |
//\_|  |_/\__,_|\__,_|\___| |_.__/ \__, | \____/ \__,_|\__,_|_|
//                                  __/ |
//                                 |___/

#include <bits/stdc++.h>
#define endl '\n'
#define all(x) (x).begin(),(x).end()
#define fi first
#define se second
using namespace std;
#define int long long

void openFile(){
    #define NAME "NAME"
    if (fopen(NAME".INP","r")==NULL) return;
    freopen(NAME".INP","r",stdin);
    freopen(NAME".OUT","w",stdout);
}

const int N=1e5;
int n,m;
int s,t,u,v;
vector<pair<int,int> > edge[N+5];
int distU[N+5];
int distV[N+5];
int dist[N+5];
int ans;

int miU[N+5];
int miV[N+5];

void djkU(){
    memset(distU,0x3f,sizeof(distU));

    distU[u]=0;

    priority_queue<pair<int,int>,vector<pair<int,int> >,greater<pair<int,int> > > pq;

    pq.push({0,u});
    while(!pq.empty()){
        int d=pq.top().fi;
        int c=pq.top().se;

        pq.pop();

        if(distU[c]<d) continue;

        for(pair<int,int> pii :edge[c]){
            int x=pii.fi;
            int w=pii.se;

            int nd=d+w;
            if(distU[x]>nd){
                distU[x]=nd;
                pq.push({nd,x});
            }
        }
    }


}

void djkV(){
    memset(distV,0x3f,sizeof(distV));
    distV[v]=0;

    priority_queue<pair<int,int>,vector<pair<int,int> >,greater<pair<int,int> > > pq;

    pq.push({0,v});
    while(!pq.empty()){
        int d=pq.top().fi;
        int c=pq.top().se;

        pq.pop();

        if(distV[c]<d) continue;

        for(pair<int,int> pii :edge[c]){
            int x=pii.fi;
            int w=pii.se;

            int nd=d+w;
            if(distV[x]>nd){
                distV[x]=nd;
                pq.push({nd,x});
            }
        }
    }
}

void djk2(int st,int ed){
    memset(dist,0x3f,sizeof(dist));
    memset(miU,0x3f,sizeof(miU));
    memset(miV,0x3f,sizeof(miV));

    priority_queue<pair<int,int>,vector<pair<int,int> >,greater<pair<int,int> > > pq;
    pq.push({0,st});

    miU[st]=distU[st];
    miV[st]=distV[st];

    while(!pq.empty()){
        int d=pq.top().fi;
        int c=pq.top().se;

        pq.pop();

        if(dist[c]<d) continue;

        for(pair<int,int> pii:edge[c]){
            int x=pii.fi;
            int w=pii.se;
            int nd=d+w;

            if(dist[x]>nd){
                dist[x]=nd;
                miU[x]=min(distU[x],miU[c]);
                miV[x]=min(distV[x],miV[c]);
                pq.push({nd,x});


            }

            else if(dist[x]==nd){
                if(min(distU[x],miU[c])+min(distV[x],miV[c])<miU[x]+miV[x]){
                    miU[x]=min(distU[x],miU[c]);
                    miV[x]=min(distV[x],miV[c]);
                }
                pq.push({nd,x});
            }
        }
    }

    ans=min(ans,miU[ed]+miV[ed]);
}

void solve(){
    cin>>n>>m>>s>>t>>u>>v;

    for(int i=1;i<=m;i++){
        int u,v,w; cin>>u>>v>>w;
        edge[u].push_back({v,w});
        edge[v].push_back({u,w});
    }

    djkU();
    djkV();
    ans=distU[v];

    djk2(s,t);
    djk2(t,s);

    cout<<ans;
}

signed main(){
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

    openFile();
    solve();

    return 0;
}

Compilation message (stderr)

commuter_pass.cpp: In function 'void openFile()':
commuter_pass.cpp:21:12: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   21 |     freopen(NAME".INP","r",stdin);
      |     ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~
commuter_pass.cpp:22:12: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   22 |     freopen(NAME".OUT","w",stdout);
      |     ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~

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