Submission #479735

#	Time	Username	Problem	Language	Result	Execution time	Memory
479735		Yuisuyuno	Commuter Pass (JOI18_commuter_pass)	C++14	31 / 100	934 ms	43456 KiB

commuter_pass

//Nguyen Huu Hoang Minh
#include <bits/stdc++.h>
#define sz(x) int(x.size())
#define all(x) x.begin(),x.end()
#define reset(x) memset(x, 0,sizeof(x))
#define pb push_back
#define mp make_pair
#define fi first
#define se second
#define N 100005
#define remain(x) if (x > MOD) x -= MOD
#define ii pair<int, int>
#define iiii pair< ii , ii >
#define viiii vector< iiii >
#define vi vector<int>
#define vii vector< ii >
#define bit(x, i) (((x) >> (i)) & 1)
#define Task "test"
#define int long long

using namespace std;

typedef long double ld;
const int inf = 1e10;
const int minf = -1e10;

int n, m;
int s, t, u, v;
vector<ii> g[N];
int ds[N], dv[N], dt[N];
int dad[N];
map<ii, int> id;
bool is_edge[200005];

void readfile()
{
    ios_base::sync_with_stdio(false);
    cin.tie(0);cout.tie(0);
    if (fopen(Task".inp","r"))
    {
        freopen(Task".inp","r",stdin);
        //freopen(Task".out","w",stdout);
    }
    cin >> n >> m >> s >> t >> u >> v;
    for(int i=1; i<=m; i++){
        int u, v, z;
        cin >> u >> v >> z;
        g[u].pb(ii(v,z));
        g[v].pb(ii(u,z));
        id[ii(u,v)] = i;
        id[ii(v,u)] = i;
    }
}

void djk(){
    for(int i=1; i<=n; i++) ds[i] = dv[i] = dt[i] = 1e17;
    ds[s] = 0;
    priority_queue<ii, vii, greater<ii>> q;
    q.push(ii(0,s));
    dad[s] = -1;
    while (q.size()){
        int du = q.top().fi;
        int u = q.top().se;
        q.pop();
        if (du!=ds[u]) continue;
        for(auto i : g[u]){
            int v = i.fi;
            int uv = i.se;
            if (ds[v] > du+uv){
                ds[v] = du+uv;
                dad[v] = u;
                q.push(ii(ds[v],v));
            }
        }
    }
    int Min_dis = ds[t];
    dt[t] = 0;
    q.push(ii(0,t));
    while (q.size()){
        int u = q.top().se;
        int du = q.top().fi;
        q.pop();
        if (du!=dt[u]) continue;
        for(auto i : g[u]){
            int v = i.fi;
            int uv = i.se;
            if (dt[v] > du+uv){
                dt[v] = du+uv;
                q.push(ii(dt[v],v));
            }
        }
    }
    dv[v] = 0;
    q.push(ii(dv[v],v));
    while (q.size()){
        int u = q.top().se;
        int du = q.top().fi;
        q.pop();
        if (dv[u]!=du) continue;
        for(auto i : g[u]){
            int v = i.fi;
            int uv = i.se;
            bool is_free = false;
            if (ds[v]+dt[u]+uv==Min_dis || ds[u]+dt[v]+uv==Min_dis){
                is_free = true;
            }
            if (dv[v] > du + (is_free ? 0 : uv)){
                dv[v] = du + (is_free ? 0 : uv);
                q.push(ii(dv[v],v));
            }
        }
    }
    if (u==s || n<=300) cout << dv[s];
    else{
        int tmp = t;
        while (dad[tmp]!=-1){
            int ntmp = dad[tmp];
            int idx = id[ii(tmp,ntmp)];
            is_edge[idx] = 1;
            tmp = ntmp;
        }
        for(int i=1; i<=n; i++) dv[i] = 1e17;
        dv[v] = 0;
        q.push(ii(dv[v],v));
        while (q.size()){
            int u = q.top().se;
            int du = q.top().fi;
            q.pop();
            if (dv[u]!=du) continue;
            for(auto i : g[u]){
                int v = i.fi;
                int uv = i.se;
                bool is_free = is_edge[id[ii(u,v)]];
                if (dv[v] > du + (is_free ? 0 : uv)){
                    dv[v] = du + (is_free ? 0 : uv);
                    q.push(ii(dv[v],v));
                }
            }
        }
        cout << dv[u];
    }
}

void proc()
{
    djk();
}

signed main()
{
    readfile();
    proc();
    return 0;
}

Compilation message (stderr)

commuter_pass.cpp: In function 'void readfile()':
commuter_pass.cpp:41:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   41 |         freopen(Task".inp","r",stdin);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~

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