Submission #333271

#	Time	Username	Problem	Language	Result	Execution time	Memory
333271		anonymous	Commuter Pass (JOI18_commuter_pass)	C++14	100 / 100	478 ms	22368 KiB

commuter_pass

#include <iostream>
#include <vector>
#include <queue>
#include <utility>
#define MAXN 100005
#define LL long long
using namespace std;
int N, M, A, B, U, V;
LL db[MAXN], du[MAXN], dv[MAXN];
LL da[MAXN], umin[MAXN], best = 1LL<<60;
vector <pair<int,LL> > adj[MAXN];
priority_queue <pair<LL,int> > PQ;

void dijkstra(int src, LL* d) {
    for (int i=1; i<=N; i++) {
        d[i] = 1LL<<60;
    }
    d[src] = 0;
    PQ.push({0, src});
    while (PQ.size()) {
        LL w = -PQ.top().first, v = PQ.top().second;
        PQ.pop();
        if (w != d[v]) {continue;}
        for (auto e: adj[v]) {
             if (e.second + d[v] < d[e.first]) {
                d[e.first] = e.second + d[v];
                PQ.push({-d[e.first], e.first});
             }
        }
    }
}

void slv() {
    for (int i=1; i<=N; i++) {
        da[i] = 1LL<<60;
        umin[i] = du[i];
    }
    da[A] = 0, umin[A] = du[A]; //need relax d(u,v)?
    PQ.push({0, A});
    while (PQ.size()) {
        LL  w = -PQ.top().first, v = PQ.top().second;
        PQ.pop();
        if (w != da[v]) {continue;}
        for (auto e: adj[v]) {
             if (e.second + da[v] < da[e.first]) {
                da[e.first] = e.second + da[v];
                umin[e.first] = min(du[e.first], umin[v]);
                PQ.push({-da[e.first], e.first});
             } else if (e.second + da[v] == da[e.first]) {
                umin[e.first] = min(du[e.first], min(umin[e.first],umin[v]));
             }
        }
        if (da[v] + db[v] == db[A]) {
            best = min(best, umin[v] + dv[v]);
        }
    }
}

int main() {
    //freopen("passin.txt","r",stdin);
    scanf("%d %d\n%d %d\n%d %d",&N,&M,&A,&B,&U,&V);
    for (int i=0; i<M; i++) {
        int a,b,c;
        scanf("%d %d %d",&a,&b,&c);
        adj[a].push_back({b,c});
        adj[b].push_back({a,c});
    }

    dijkstra(B, db);
    dijkstra(U, du);
    dijkstra(V, dv);
    best = du[V];
    slv();
    swap(A,B);
    for (int i=1; i<=N; i++) {
        db[i] = da[i];
    }
    slv();

    printf("%lld",best);
}

Compilation message (stderr)

commuter_pass.cpp: In function 'int main()':
commuter_pass.cpp:61:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   61 |     scanf("%d %d\n%d %d\n%d %d",&N,&M,&A,&B,&U,&V);
      |     ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
commuter_pass.cpp:64:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   64 |         scanf("%d %d %d",&a,&b,&c);
      |         ~~~~~^~~~~~~~~~~~~~~~~~~~~

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