Submission #306794

#	Time	Username	Problem	Language	Result	Execution time	Memory
306794		exdan	Commuter Pass (JOI18_commuter_pass)	C++14	0 / 100	2098 ms	19188 KiB

commuter_pass

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<ll, ll> ii;

ll n, m, s, t, u, v, a, b, c;
vector<ii> adj[100005];
ll dist_s[100005], dist_t[100005], dist_u[100005], dist_v[100005];
ll visited[2][100005];
ll mini[2][100005];
priority_queue<ii> pq;


void dij(ll *dist, ll node){
    pq.push(make_pair(0, node)); ///dist, node
    dist[node] = 0;
    //printf("\n");

    while (!pq.empty()){
        ii now = pq.top();
        pq.pop();
        //printf("%lld %lld\n", now.first, now.second);
        if (now.first == dist[now.second]){
            for (ii neigh: adj[now.second]){
                if (neigh.second + dist[now.second] < dist[neigh.first]){
                    dist[neigh.first] = neigh.second + dist[now.second];
                    pq.push(make_pair(dist[neigh.first], neigh.first));
                }
            }
        }
    }
}

ll dfs_s(ll node){
    if (visited[0][node] == 1) return mini[0][node];
    visited[0][node] = 1;
    if (node == s){
        mini[0][s] = dist_u[s];
        return dist_u[s];
    }
    ll low = dist_u[node];
    for (ii neigh:adj[node]){
        if (visited[0][neigh.first] == 1) continue;
        if (dist_s[neigh.first] + neigh.second == dist_s[node]){
            ll posmin = dfs_s(neigh.first);
            low = min(low, posmin);
        }
    }
    mini[0][node] = low;
    return mini[0][node];
}

ll dfs_t(ll node){
    if (visited[1][node] == 1) return mini[1][node];
    visited[1][node] = 1;
    if (node == t){
        mini[1][t] = dist_u[t];
        return dist_u[t];
    }
    ll low = dist_u[node];
    for (ii neigh:adj[node]){
        if (visited[1][neigh.first] == 1) continue;
        if (dist_t[neigh.first] + neigh.second == dist_t[node]){
            ll posmin = dfs_t(neigh.first);
            low = min(low, posmin);
        }
    }
    mini[1][node] = low;
    return mini[1][node];
}

int main(){
    scanf("%lld%lld", &n, &m);
    scanf("%lld%lld", &s, &t);
    scanf("%lld%lld", &u, &v);
    for (ll i = 0; i <= n; ++i){
        dist_s[i] = 1023456789102345;
        dist_t[i] = 1023456789102345;
        dist_u[i] = 1023456789102345;
        dist_v[i] = 1023456789102345;
        mini[0][i] = 1023456789102345;
        mini[1][i] = 1023456789102345;
    }
    for (ll i = 0; i < m; ++i){
        scanf("%lld%lld%lld", &a, &b, &c);
        adj[a].push_back(make_pair(b,c));
        adj[b].push_back(make_pair(a,c));
    }

    dij(dist_s, s);
    dij(dist_t, t);
    dij(dist_u, u);
    dij(dist_v, v);

    dfs_s(t);
    dfs_t(s);

    ll out = dist_u[v];

    for (ll i = 1; i <= n; ++i){
        out = min(out, mini[0][i] + dist_v[i]);
        out = min(out, mini[1][i] + dist_v[i]);
        //printf("%lld %lld %lld %lld %lld %lld %lld\n", i, dist_s[i], dist_t[i], dist_u[i], dist_v[i], mini[0][i], mini[1][i]);
    }

    printf("%lld", out);

    return 0;
}

Compilation message (stderr)

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

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