Submission #307244

#	Time	Username	Problem	Language	Result	Execution time	Memory
307244		Spongiforma	Commuter Pass (JOI18_commuter_pass)	C++17	0 / 100	444 ms	31888 KiB

commuter_pass

#include <bits/stdc++.h>
#define INF LLONG_MAX/2
#define sacnf scanf
#define scnf scanf
#define scnaf scanf
#define CRLF <<'\n';
#define ALL(v) v.begin,v.end()
#define SIZE(v) (int)v.size()
#define PRPAIR(x) x.first << x.second
#define DEBUG(x) do { std::cerr <<(x)<<'\n'; } while (0)
#define rep(i,a,b) for(int i=(int)(a);i<(int)(b);++i)
using namespace std;
typedef long long ll;
typedef pair<ll,ll> ii;
typedef pair<int,ii> pip;
typedef vector<ll> vi;
#define N 100005
#define M 200005

int n,m,s,t,u,v;
vi ds,dt,du,dv;
vector<ii> adj[N];

void sssp(int i,vi &dist){
    dist.assign(n,INF);
    dist[i] = 0;
    priority_queue<ii,vector<ii>,greater<ii>> q;
    q.push({0,i});
    while(!q.empty()){
        ii a=q.top(); q.pop();
        ll d = a.first, u = a.second;
        if (dist[u] < d)
            continue;
        for(auto v: adj[u]){
            if (dist[u] + v.second < dist[v.first]){
                dist[v.first] = dist[u] + v.second;
                q.push({dist[v.first],v.first});
            }
        }
    }
}


bitset<N> onsp,vis;

vi g[N],g2[N];

void bs(int i){
    onsp[i] = 1;
    vis[i] = 1;
    if (i == s)
        return;
    for(auto v: adj[i]){
        if (!vis[v.first] && ds[v.first] + v.second == ds[i]){
            g2[i].push_back(v.first);
            g[v.first].push_back(i);
            bs(v.first);
        }
    }
}



ll dfs(ll utosp,int i){
    if (i == t)
        return utosp + dt[v];
    vis[i] = 1;
    ll minv=utosp+dv[i];
    for(auto v: g[i]){
        if (!vis[v] && onsp[v])
            minv = min(dfs(min(utosp,du[v]),v),minv);
    }
    return minv;
}

ll dfs2(ll utosp,int i){
    if (i == t)
        return utosp + ds[v];
    vis[i] = 1;
    ll minv=utosp+dv[i];
    for(auto v: g2[i]){
        if (!vis[v] && onsp[v])
            minv = min(dfs2(min(utosp,du[v]),v),minv);
    }
    return minv;
}


int main(){
    scanf("%d%d%d%d%d%d",&n,&m,&s,&t,&u,&v);
    s--,t--,u--,v--;

    rep(i,0,m){
        ll a,b,c;
        scanf("%lld%lld%lld",&a,&b,&c);
        a--,b--;
        adj[a].emplace_back(b,c);
        adj[b].emplace_back(a,c);
    }
    sssp(s,ds),sssp(t,dt),sssp(u,du),sssp(v,dv);
    //    rep(i,0,n){
        //cout << i+1 << ' ' << ds[i] << '\n';
    //    }
    vis.reset();
    bs(t);
    //    rep(i,0,n){
      //cout << i+1 << " " << onsp[i] << '\n';
    //    }
    vis.reset();
    ll ans = dfs(du[s],s);
    //    cout << du[s];
    vis.reset();
    ans = min(ans,dfs2(du[t],t));
    ans = min(du[v],ans);
    cout << ans;
}

Compilation message (stderr)

commuter_pass.cpp: In function 'int main()':
commuter_pass.cpp:90:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   90 |     scanf("%d%d%d%d%d%d",&n,&m,&s,&t,&u,&v);
      |     ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
commuter_pass.cpp:95:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   95 |         scanf("%lld%lld%lld",&a,&b,&c);
      |         ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~

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