oj.uz

답안 #915042

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
915042 2024-01-23T08:35:33 Z asdfGuest Commuter Pass (JOI18_commuter_pass) C++14
31 / 100
 494 ms 45132 KB 
#include <iostream>
#include <algorithm>
#include <vector>
#include <queue>

using namespace std;

#define INF (1000000000ll * 200000ll)

typedef long long ll;

struct adj_t {
    int nx;
    ll w;
};

int n, m;
vector<adj_t> adj[100001], adj_inv[100001];

vector<ll> dijkstra(int start, vector<adj_t> *adj_mat) {
    vector<ll> dist(n + 1, INF);
    priority_queue<pair<ll, int>> heap;
    
    heap.push({-0ll, start});
    dist[start] = 0ll;

    while (!heap.empty()) {
        int nw = heap.top().second;
        ll d = -heap.top().first;
        heap.pop();
        
        if (d > dist[nw])
            continue;
        
        for (int i = 0; i < adj_mat[nw].size(); i++) {
            auto nex = adj_mat[nw][i];
            ll new_cost = d + nex.w;

            if (new_cost < dist[nex.nx]) {
                heap.push({-new_cost, nex.nx});
                dist[nex.nx] = new_cost;
            }
        }
    }

    return dist;
}
vector<pair<int, int>> shortest_path(int start, int end, vector<adj_t> *adj_mat) {
    vector<ll> dist(n + 1, INF);
    vector<int> memo[100001];
    vector<pair<int, int>> edge;

    priority_queue<pair<ll, int>> heap;
    
    heap.push({-0, start});
    dist[start] = 0;

    while (!heap.empty()) {
        int nw = heap.top().second;
        ll d = -heap.top().first;
        heap.pop();

        if (d > dist[nw])
            continue;
        
        for (int i = 0; i < adj_mat[nw].size(); i++) {
            auto nex = adj_mat[nw][i];
            ll new_cost = d + nex.w;

            if (new_cost < dist[nex.nx]) {
                heap.push({-new_cost, nex.nx});
                dist[nex.nx] = new_cost;

                memo[nex.nx].clear();
                memo[nex.nx].push_back(nw);
            }
            else if (new_cost == dist[nex.nx])
                memo[nex.nx].push_back(nw);
        }
    }

    bool visit[100001] = {false};
    queue<int> bfsQ;

    bfsQ.push(end);
    visit[end] = true;

    while (!bfsQ.empty()) {
        int nw = bfsQ.front();
        bfsQ.pop();

        for (int i = 0; i < memo[nw].size(); i++) {
            int nex = memo[nw][i];

            if (!visit[nex]) {
                bfsQ.push(nex);
                visit[nex] = true;
            }

            edge.push_back({nex, nw});
        }
    }

    return edge;
}

int main(void) {
    int s, t, u, v;
    scanf("%d %d %d %d %d %d", &n, &m, &s, &t, &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, (ll)c});
        adj[b].push_back({a, (ll)c});
        adj_inv[a].push_back({b, (ll)c});
        adj_inv[b].push_back({a, (ll)c});
    }

    auto edge = shortest_path(s, t, adj);
    for (int i = 0; i < edge.size(); i++) {
        adj[edge[i].first].push_back({edge[i].second, 0ll});
        adj_inv[edge[i].second].push_back({edge[i].first, 0ll});
    }
    
    auto udis1 = dijkstra(u, adj), vdis1 = dijkstra(v, adj_inv);
    auto udis2 = dijkstra(u, adj_inv), vdis2 = dijkstra(v, adj);
    ll ans = INF;
    
    for (int i = 1; i <= n; i++)
        ans = min(ans, min(udis1[i] + vdis1[i], udis2[i] + vdis2[i]));

    printf("%lld\n", ans);
  
    return 0;
}

Compilation message

commuter_pass.cpp: In function 'std::vector<long long int> dijkstra(int, std::vector<adj_t>*)':
commuter_pass.cpp:35:27: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<adj_t>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   35 |         for (int i = 0; i < adj_mat[nw].size(); i++) {
      |                         ~~^~~~~~~~~~~~~~~~~~~~
commuter_pass.cpp: In function 'std::vector<std::pair<int, int> > shortest_path(int, int, std::vector<adj_t>*)':
commuter_pass.cpp:66:27: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<adj_t>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   66 |         for (int i = 0; i < adj_mat[nw].size(); i++) {
      |                         ~~^~~~~~~~~~~~~~~~~~~~
commuter_pass.cpp:92:27: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   92 |         for (int i = 0; i < memo[nw].size(); i++) {
      |                         ~~^~~~~~~~~~~~~~~~~
commuter_pass.cpp: In function 'int main()':
commuter_pass.cpp:121:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  121 |     for (int i = 0; i < edge.size(); i++) {
      |                     ~~^~~~~~~~~~~~~
commuter_pass.cpp:109:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  109 |     scanf("%d %d %d %d %d %d", &n, &m, &s, &t, &u, &v);
      |     ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
commuter_pass.cpp:113:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  113 |         scanf("%d %d %d", &a, &b, &c);
      |         ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~

Subtask #1
16.0 / 16.0

# 결과 실행 시간 메모리 Grader output
1 Correct 388 ms 39124 KB Output is correct
2 Correct 494 ms 39600 KB Output is correct
3 Correct 410 ms 42820 KB Output is correct
4 Correct 396 ms 39152 KB Output is correct
5 Correct 393 ms 40960 KB Output is correct
6 Correct 453 ms 38128 KB Output is correct
7 Correct 395 ms 41096 KB Output is correct
8 Correct 408 ms 40672 KB Output is correct
9 Correct 376 ms 38036 KB Output is correct
10 Correct 318 ms 38180 KB Output is correct
11 Correct 168 ms 27776 KB Output is correct
12 Correct 377 ms 37808 KB Output is correct

Subtask #2
15.0 / 15.0

# 결과 실행 시간 메모리 Grader output
1 Correct 419 ms 39424 KB Output is correct
2 Correct 407 ms 39496 KB Output is correct
3 Correct 441 ms 40140 KB Output is correct
4 Correct 428 ms 40304 KB Output is correct
5 Correct 464 ms 39512 KB Output is correct
6 Correct 470 ms 42380 KB Output is correct
7 Correct 438 ms 45132 KB Output is correct
8 Correct 409 ms 39524 KB Output is correct
9 Correct 492 ms 40052 KB Output is correct
10 Correct 454 ms 38996 KB Output is correct
11 Correct 187 ms 29916 KB Output is correct
12 Correct 422 ms 42612 KB Output is correct

Subtask #3
0 / 24.0

# 결과 실행 시간 메모리 Grader output
1 Correct 12 ms 10844 KB Output is correct
2 Correct 4 ms 7516 KB Output is correct
3 Correct 3 ms 7516 KB Output is correct
4 Correct 19 ms 13400 KB Output is correct
5 Correct 12 ms 10588 KB Output is correct
6 Correct 4 ms 7772 KB Output is correct
7 Incorrect 6 ms 7772 KB Output isn't correct
8 Halted 0 ms 0 KB -

Subtask #4
0 / 45.0

# 결과 실행 시간 메모리 Grader output
1 Correct 388 ms 39124 KB Output is correct
2 Correct 494 ms 39600 KB Output is correct
3 Correct 410 ms 42820 KB Output is correct
4 Correct 396 ms 39152 KB Output is correct
5 Correct 393 ms 40960 KB Output is correct
6 Correct 453 ms 38128 KB Output is correct
7 Correct 395 ms 41096 KB Output is correct
8 Correct 408 ms 40672 KB Output is correct
9 Correct 376 ms 38036 KB Output is correct
10 Correct 318 ms 38180 KB Output is correct
11 Correct 168 ms 27776 KB Output is correct
12 Correct 377 ms 37808 KB Output is correct
13 Correct 419 ms 39424 KB Output is correct
14 Correct 407 ms 39496 KB Output is correct
15 Correct 441 ms 40140 KB Output is correct
16 Correct 428 ms 40304 KB Output is correct
17 Correct 464 ms 39512 KB Output is correct
18 Correct 470 ms 42380 KB Output is correct
19 Correct 438 ms 45132 KB Output is correct
20 Correct 409 ms 39524 KB Output is correct
21 Correct 492 ms 40052 KB Output is correct
22 Correct 454 ms 38996 KB Output is correct
23 Correct 187 ms 29916 KB Output is correct
24 Correct 422 ms 42612 KB Output is correct
25 Correct 12 ms 10844 KB Output is correct
26 Correct 4 ms 7516 KB Output is correct
27 Correct 3 ms 7516 KB Output is correct
28 Correct 19 ms 13400 KB Output is correct
29 Correct 12 ms 10588 KB Output is correct
30 Correct 4 ms 7772 KB Output is correct
31 Incorrect 6 ms 7772 KB Output isn't correct
32 Halted 0 ms 0 KB -