Submission #307297

#	Time	Username	Problem	Language	Result	Execution time	Memory
307297		Spongiforma	Commuter Pass (JOI18_commuter_pass)	C++17	100 / 100	515 ms	28956 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];
ll mem1[N],mem2[N];

ll mutosp1(int i){
    if (mem1[i]!=-1)
        return mem1[i];
    if (i == s){
        mem1[i] = du[s];
        return mem1[i];
    }
    mem1[i] = du[i];
    for(auto v: adj[i]){
        if (dt[i] + v.second + ds[v.first] == ds[t])
            mem1[i] = min(mem1[i],mutosp1(v.first));
    }
    return mem1[i];
}
ll mutosp2(int i){
    if (mem2[i]!=-1)
        return mem2[i];

    if (i == t){
        mem2[i] = du[t];
        return mem2[i];
    }
    mem2[i] = du[i];
    for(auto v: adj[i]){
        if (ds[i] + v.second + dt[v.first] == ds[t])
            mem2[i] = min(mem2[i],mutosp2(v.first));
    }
    return mem2[i];
}

ll mem3[N],mem4[N];

ll dfs(int i){
    if (mem3[i] != -1)
        return mem3[i];
    ll minv=dv[i]+mem2[i];
    for(auto v: adj[i]){
        if (ds[i] + v.second + dt[v.first] == ds[t])
            minv = min(dfs(v.first),minv);
    }
    return mem3[i] = minv;
}


ll dfs2(int i){
    if (mem4[i] != -1)
        return mem4[i];
    ll minv=dv[i]+mem1[i];
    for(auto v: adj[i]){
        if (dt[i] + v.second + ds[v.first] == ds[t])
            minv = min(dfs2(v.first),minv);
    }
    return mem4[i]=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);
    vis.reset();
    memset(mem1,-1,sizeof mem1);
    memset(mem2,-1,sizeof mem2);
    memset(mem3,-1,sizeof mem3);
    memset(mem4,-1,sizeof mem4);
    mutosp1(t);
    mutosp2(s);
    ll ans = dfs(s);
    ans = min(ans,dfs2(t));
    ans = min(du[v],ans);
    cout << ans;
}

Compilation message (stderr)

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

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