Submission #1307680

#	Time	Username	Problem	Language	Result	Execution time	Memory
1307680		dimitris71	Commuter Pass (JOI18_commuter_pass)	C++20	100 / 100	229 ms	19292 KiB

commuter_pass

#include <cstdio>
#include <vector>
#include <algorithm>
#include <queue>
#include <utility>

using namespace std;

#define MAXNUM 1000000000
#define MAXN 100000
#define MAXM 200000
#define INF ((long long) (1e18))

struct edge {
    int x, y, len;
};

vector<long long> Dinit, Dtrans, Db, Da, Da1, Da2;
vector<vector<pair<int, int> > > G;
vector <edge> E;

void Dijkstra(int s, int N, vector<long long> &dist) {
    priority_queue<pair<long long, int> > PQ;

    for (int i = 0; i < N; i++) dist[i] = INF;       
    dist[s] = 0;

    PQ.push(make_pair(-dist[s], s));
    while (!PQ.empty()) {
        pair<long long, int> front = PQ.top();
        PQ.pop();
        long long w = -front.first, u = front.second;
        if (w > dist[u]) continue;
        for (int p = 0; p < G[u].size(); p++) {
            pair<int, int> v = G[u][p];
            long long tmp = min(dist[v.first], dist[u] + v.second);
            if (dist[v.first] > tmp) {
                dist[v.first] = tmp;
                PQ.push(make_pair(-tmp, v.first));
            }
        }
    }
}

void Dijkstra2(int s, int N, vector<long long> &dist) {
    priority_queue<pair<long long, int> > PQ;
    vector <bool> vis(N, false);

    PQ.push(make_pair(-dist[s], s));
    while (!PQ.empty()) {
        pair<long long, int> front = PQ.top();
        PQ.pop();
        long long w = -front.first, u = front.second;
        vis[u] = true;
        if (w > dist[u]) continue;
        for (int p = 0; p < G[u].size(); p++) {
            pair<int, int> v = G[u][p];
            long long tmp = min(dist[v.first], dist[u] + v.second);
            if (dist[v.first] > tmp) {
                dist[v.first] = tmp;
                PQ.push(make_pair(-dist[v.first], v.first));
                vis[v.first] =true;
            }
            if (!vis[v.first]) PQ.push(make_pair(-dist[v.first], v.first));
        }
    }
}

int main() {
    int N, M, s, t, a, b; 

    scanf("%d%d", &N, &M);
    if (N < 1 || N > MAXN || M < 1 || M > MAXM) {
        fprintf(stderr, "Error in input (N = %d, M = %d)\n", N, M);
        return 1;
    }
    scanf("%d%d", &s, &t); s--; t--;
    scanf("%d%d", &a, &b); a--; b--;

    G.resize(N); Dinit.resize(N); Dtrans.resize(N); E.resize(M);
    Da1.resize(N); Da2.resize(N); Da.resize(N); Db.resize(N);

    for (int i = 0; i < M; i++) {
        int u, v, d; 
        scanf("%d%d%d", &u, &v, &d); u--; v--;
        G[u].push_back(make_pair(v, d));
        G[v].push_back(make_pair(u, d));
        E[i].x = u; E[i].y = v; E[i].len = d;
    }

    Dijkstra(s, N, Dinit);
    Dijkstra(t, N, Dtrans);
    Dijkstra(b, N, Db);
    Dijkstra(a, N, Da);

    for (int i = 0; i < N; i++) { 
        G[i].resize(0); 
        if (Dinit[i]+Dtrans[i] == Dinit[t]) Da1[i] = Da2[i] = Da[i];
        else Da1[i] = Da2[i] = INF;
    }

    for (int i = 0; i < M; i++) {
        int u = E[i].x, v = E[i].y, d = E[i].len;

        if (Dinit[u] + Dtrans[v] + d == Dinit[t]) 
            G[u].push_back(make_pair(v, 0)); // direction u -> v, no cost
        if (Dinit[v] + Dtrans[u] + d == Dinit[t])
            G[v].push_back(make_pair(u, 0)); // direction v -> u, no cost
    }
    Dijkstra2(s, N, Da1);

    for (int i = 0; i < N; i++) G[i].resize(0); 
    for (int i = 0; i < M; i++) {
        int u = E[i].x, v = E[i].y, d = E[i].len;

        if (Dinit[u] + Dtrans[v] + d == Dinit[t])
            G[v].push_back(make_pair(u, 0)); // direction v -> u, no cost
        if (Dinit[v] + Dtrans[u] + d == Dinit[t])
            G[u].push_back(make_pair(v, 0)); // direction u -> v, no cost
    }
    Dijkstra2(t, N, Da2);

    long long res = Db[a];
    for (int i=0; i<N; i++) 
        if (Dinit[i]+Dtrans[i] == Dinit[t]) 
            res = min(res, min(Da1[i]+Db[i], Da2[i]+Db[i]));
    printf("%lld\n", res);
    return 0;
}

Compilation message (stderr)

commuter_pass.cpp: In function 'int main()':
commuter_pass.cpp:72:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   72 |     scanf("%d%d", &N, &M);
      |     ~~~~~^~~~~~~~~~~~~~~~
commuter_pass.cpp:77:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   77 |     scanf("%d%d", &s, &t); s--; t--;
      |     ~~~~~^~~~~~~~~~~~~~~~
commuter_pass.cpp:78:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   78 |     scanf("%d%d", &a, &b); a--; b--;
      |     ~~~~~^~~~~~~~~~~~~~~~
commuter_pass.cpp:85:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   85 |         scanf("%d%d%d", &u, &v, &d); u--; v--;
      |         ~~~~~^~~~~~~~~~~~~~~~~~~~~~

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