Submission #1076654

#	Time	Username	Problem	Language	Result	Execution time	Memory
1076654		_no_name	Commuter Pass (JOI18_commuter_pass)	C++17	100 / 100	184 ms	20372 KiB

commuter_pass

//Ai_2007
//Make the impossible possible
#include<bits/stdc++.h>
#define ll long long
#define fo(i,m,n) for(int i=m; i<=n; i++)
#define fod(i,m,n) for(int i=m; i>=n; i--)
#define fi first
#define se second
#define Nmax 1000001
#define pb push_back
#define pii pair<int,int>
#define getbit(i,j) ((i>>j)&1)
#define onbit(i,j) (i=(1<<j))
#define offbit(i,j) (i^=(1<<j))
#define pll pair<ll,ll>
#define plp pair<ll,pii>
using namespace std;
const int N=1e5+5;
int n,m,s,t,U,V;
vector<pii> adj[N];
ll dis[2][N],ans,dp[2][N],d[N];
bool vst[N];
void dij1(int st, int id)
{
    fo(i,1,n) {
        dis[id][i]=1e18;
        vst[i]=0;
    }
    dis[id][st]=0;
    priority_queue<pll, vector<pll>,greater<pll>> q;
    q.push({0,st});
    while(!q.empty()){
        int u=q.top().se;
        q.pop();
        if(vst[u]) continue;
        vst[u]=1;
        for(auto it:adj[u]){
            int v=it.fi;
            int w=it.se;
            if(dis[id][v] > dis[id][u] + w){
                dis[id][v]=dis[id][u] + w;
                q.push({dis[id][v],v});
            }
        }
    }
}
void dij2(int st, int en)
{
    fo(i,0,n){
        vst[i]=0;
        dp[0][i]=dp[1][i]=1e18;
        d[i]=1e18;
    }
    priority_queue<pll,vector<pll>,greater<pll>> q;
    d[st]=0;
    q.push({0,st});
    dp[0][st]=dis[0][st];
    dp[1][st]=dis[1][st];
    while(!q.empty()){
        int u=q.top().se;
        q.pop();
        if(vst[u]) continue;
        vst[u]=1;
            for(auto it:adj[u]){
                int v=it.fi;
                int w=it.se;
                if(d[v] > d[u] + w){
                    d[v]=d[u] + w;
                    dp[0][v]=min(dis[0][v], dp[0][u]);
                    dp[1][v]=min(dis[1][v], dp[1][u]);
                    q.push({d[v],v});
                }
                else if(d[v]==d[u]+w){
                    if(min(dis[0][v], dp[0][u]) + min(dis[1][v], dp[1][u])<dp[0][v] + dp[1][v]){
                    dp[0][v]=min(dis[0][v], dp[0][u]);
                    dp[1][v]=min(dis[1][v], dp[1][u]);
                    }
                }
            }
    }
    ans=min(ans, dp[0][en] + dp[1][en]);
}
void solve()
{
    cin>>n>>m>>s>>t>>U>>V;
    fo(i,1,m){
        int u,v,w;
        cin>>u>>v>>w;
        adj[u].pb({v,w});
        adj[v].pb({u,w});
    }
    dij1(U,0);
    dij1(V,1);
    ans=dis[0][V];
//    ans=min(ans, dis[1][U]);
    dij2(s,t);
//    dij2(t,s);
    if(ans!=1e18) cout<<ans;
    else cout<<-1;
}
main()
{
    //freopen("pathlib.inp","r",stdin);
    //freopen("pathlib.out","w",stdout);
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    solve();
    return 0;
}

Compilation message (stderr)

commuter_pass.cpp:101:1: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
  101 | main()
      | ^~~~

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