Submission #1307898

#	Time	Username	Problem	Language	Result	Execution time	Memory
1307898		dimitris71	Commuter Pass (JOI18_commuter_pass)	C++20	100 / 100	310 ms	16132 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(-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] || w == INF) 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 solve_large(int N, int M, int t, int a, int b) {

    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
        }
        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
        }
        else {
            G[v].push_back(make_pair(u, d)); // direction v -> u, full cost
            G[u].push_back(make_pair(v, d)); // direction u -> v, full cost
        }
    }   
    
    Dijkstra(a, N, Dinit);
    Dijkstra(b, N, Dtrans);

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

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);
    
    if (N > 300) { solve_large(N, M, t, a, b); return 0; }
    
    vector<long long> Da(N), Db(N);
    Dijkstra(a, N, Da);
    Dijkstra(b, N, Db);
    long long res = Da[b];
    
    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
        else if (Dinit[v] + Dtrans[u] + d == Dinit[t])
            G[v].push_back(make_pair(u, 0)); // direction v -> u, no cost
    }

    vector <long long> Ddag(N); 
    for (int x=0; x<N; x++) {
        if (Dinit[x] + Dtrans[x] != Dinit[t]) continue;
        Dijkstra(x, N, Ddag);
        for (int y=0; y<N; y++) {
            if (Ddag[y] == INF) continue; 
            res = min(res, min(Da[x]+Db[y], Db[x]+Da[y]));
        }
    }
    printf("%lld\n", res);
    return 0;
}

Compilation message (stderr)

commuter_pass.cpp: In function 'int main()':
commuter_pass.cpp:75:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   75 |     scanf("%d%d", &N, &M);
      |     ~~~~~^~~~~~~~~~~~~~~~
commuter_pass.cpp:80:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   80 |     scanf("%d%d", &s, &t); s--; t--;
      |     ~~~~~^~~~~~~~~~~~~~~~
commuter_pass.cpp:81:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   81 |     scanf("%d%d", &a, &b); a--; b--;
      |     ~~~~~^~~~~~~~~~~~~~~~
commuter_pass.cpp:87:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   87 |         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