Submission #1307603

#	Time	Username	Problem	Language	Result	Execution time	Memory
1307603		dimitris71	Commuter Pass (JOI18_commuter_pass)	C++20	31 / 100	268 ms	16156 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;
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(0, 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));
            }
        }
    }
}

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);
    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);
    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[u].push_back(make_pair(v, 0)); // direction u -> v, no cost
            G[v].push_back(make_pair(u, d)); // direction v -> u, full cost
            fprintf(stderr, "%d %d %d\n", u+1, v+1, 0);
        }
        else if (Dinit[v] + Dtrans[u] + d == Dinit[t]) {
            G[v].push_back(make_pair(u, 0)); // direction v -> u, no cost
            G[u].push_back(make_pair(v, d)); // direction u -> v, full cost
            fprintf(stderr, "%d %d %d\n", v+1, u+1, 0);
        }
        else { 
            G[u].push_back(make_pair(v, d)); // direction u -> v, full cost
            G[v].push_back(make_pair(u, d)); // direction v -> u, full cost
        }
    }
    //for (int i=0; i<N; i++) {
    //    for (int j=0; j<G[i].size(); j++)
    //        fprintf(stderr, "%d %d %d\n", i+1, G[i][j].first+1, G[i][j].second);
    // }

    Dijkstra(a, N, Dinit);
    Dijkstra(b, N, Dtrans);

    printf("%lld\n", min(Dinit[b], Dtrans[a]));
    return 0;
}

Compilation message (stderr)

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

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