oj.uz

답안 #399846

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
399846 2021-05-06T17:54:50 Z fvogel499 Commuter Pass (JOI18_commuter_pass) C++14
24 / 100
 509 ms 27312 KB 
#include <iostream>
#include <vector>
#include <queue>
#include <set>
#include <algorithm>

using namespace std;

#define pii pair<int, int>
#define siz 100000
#define inf 1e18
#define int long long

int distFromB [siz];
int distFromA [siz];
int distFromDest [siz][4];

struct cdfb { bool operator()(int a, int b) { return (distFromB[a] > distFromB[b]); } };

struct cdfa { bool operator()(int a, int b) { return (distFromA[a] > distFromA[b]); } };

struct cdfd { bool operator()(pii a, pii b) { return (distFromDest[a.first][a.second] > distFromDest[b.first][b.second]); } };

int32_t main() {
    int nbNodes, nbEdges;
    cin >> nbNodes >> nbEdges;
    int passA, passB;
    cin >> passA >> passB;
    passA--;
    passB--;
    int origin, destination;
    cin >> origin >> destination;
    origin--;
    destination--;

    vector<vector<pii>> graph(nbNodes);
    for (int i = 0; i < nbEdges; i++) {
        int la, lb, lw;
        cin >> la >> lb >> lw;
        la--;
        lb--;
        graph[la].push_back(pii(lb, lw));
        graph[lb].push_back(pii(la, lw));
    }

    bool proc [nbNodes];
    for (int i = 0; i < nbNodes; i++) {
        proc[i] = false;
        distFromB[i] = inf;
    }
    priority_queue<int, vector<int>, cdfb> pq1;
    distFromB[passB] = 0;
    pq1.push(passB);
    while (!pq1.empty()) {
        int cn = pq1.top();
        pq1.pop();
        if (proc[cn]) continue;
        proc[cn] = true;
        for (pii ne : graph[cn]) {
            int nn = ne.first;
            int nd = distFromB[cn]+ne.second;
            if (nd < distFromB[nn]) {
                distFromB[nn] = nd;
                pq1.push(nn);
            }
        }
    }

    for (int i = 0; i < nbNodes; i++) {
        proc[i] = false;
        distFromA[i] = inf;
    }
    priority_queue<int, vector<int>, cdfa> pq2;
    distFromA[passA] = 0;
    pq2.push(passA);
    while (!pq2.empty()) {
        int cn = pq2.top();
        pq2.pop();
        if (proc[cn]) continue;
        proc[cn] = true;
        for (pii ne : graph[cn]) {
            int nn = ne.first;
            int nd = distFromA[cn]+ne.second;
            if (nd < distFromA[nn]) {
                distFromA[nn] = nd;
                pq2.push(nn);
            }
        }
    }

    set<pii> stbEdges;
    for (int i = 0; i < nbNodes; i++) {
        for (pii j : graph[i]) {
            if (distFromB[i] < distFromB[j.first] and distFromB[i]+distFromA[j.first]+j.second == distFromB[passA]) {
                stbEdges.insert(pii(i, j.first));
            }
        }
    }

    bool procState [nbNodes][4];
    for (int i = 0; i < nbNodes; i++) for (int j = 0; j < 4; j++) {
        procState[i][j] = false;
        distFromDest[i][j] = inf;
    }
    priority_queue<pii, vector<pii>, cdfd> q;
    distFromDest[origin][0] = 0;
    q.push(pii(origin, 0));
    while (!q.empty()) {
        int cn = q.top().first;
        int cs = q.top().second;
        q.pop();
        if (procState[cn][cs]) continue;
        proc[cn] = true;
        if (cn == destination) {
            cout << distFromDest[cn][cs];
            return 0;
        }
        for (pii ne : graph[cn]) {
            int nn = ne.first;
            if (cs != 3 and cs != 2 and stbEdges.find(pii(cn, nn)) != stbEdges.end()) {
                int nd = distFromDest[cn][cs];
                int ns = 1;
                if (nd < distFromDest[nn][ns]) {
                    distFromDest[nn][ns] = nd;
                    q.push(pii(nn, ns));
                }
            }
            else if (cs != 3 and cs != 1 and stbEdges.find(pii(nn, cn)) != stbEdges.end()) {
                int nd = distFromDest[cn][cs];
                int ns = 2;
                if (nd < distFromDest[nn][ns]) {
                    distFromDest[nn][ns] = nd;
                    q.push(pii(nn, ns));
                }
            }
            int nd = distFromDest[cn][cs]+ne.second;
            int ns = 0;
            if (cs != 0) ns = 3;
            if (nd < distFromDest[nn][ns]) {
                distFromDest[nn][ns] = nd;
                q.push(pii(nn, ns));
            }
        }
    }

    int d = 0;
    d++;
}

Subtask #1
0 / 16.0

# 결과 실행 시간 메모리 Grader output
1 Correct 482 ms 27312 KB Output is correct
2 Incorrect 509 ms 26808 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #2
0 / 15.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 377 ms 23920 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
24.0 / 24.0

# 결과 실행 시간 메모리 Grader output
1 Correct 26 ms 2508 KB Output is correct
2 Correct 2 ms 336 KB Output is correct
3 Correct 1 ms 332 KB Output is correct
4 Correct 42 ms 3808 KB Output is correct
5 Correct 25 ms 2024 KB Output is correct
6 Correct 2 ms 332 KB Output is correct
7 Correct 4 ms 460 KB Output is correct
8 Correct 5 ms 576 KB Output is correct
9 Correct 3 ms 460 KB Output is correct
10 Correct 26 ms 1996 KB Output is correct
11 Correct 1 ms 332 KB Output is correct
12 Correct 1 ms 332 KB Output is correct
13 Correct 2 ms 332 KB Output is correct
14 Correct 2 ms 332 KB Output is correct
15 Correct 2 ms 332 KB Output is correct

Subtask #4
0 / 45.0

# 결과 실행 시간 메모리 Grader output
1 Correct 482 ms 27312 KB Output is correct
2 Incorrect 509 ms 26808 KB Output isn't correct
3 Halted 0 ms 0 KB -