oj.uz

답안 #893215

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
893215 2023-12-26T18:08:49 Z eysbutno 악어의 지하 도시 (IOI11_crocodile) C++11
0 / 100
 1 ms 4444 KB 
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using pii = pair<int, int>;
using pll = pair<ll, ll>;
#define all(x) begin(x), end(x)
#define sz(x) (int) (x).size()
#define smin(a, b) a = min(a, b)
#define smax(a, b) a = max(a, b)
#define pb push_back
#define ins insert
#define f first 
#define s second 

int travel_plan(int N, int M, int R[][2], 
    int L[], int k, int p[]) {
    const ll INF = 1e18;
    int n = N, m = M;
    vector<vector<pii>> adj(n);
    for (int i = 0; i < m; i++) {
        int x = R[i][0], y = R[i][1],
            w = L[i];
        adj[x].pb({y, w});
        adj[y].pb({x, w});
    }
    vector<vector<ll>> dist(2, 
        vector<ll>(n, INF));
    priority_queue<pll> pq;
    for (int i = 0; i < k; i++) {
        pq.push({0, p[i]});
        dist[0][p[i]] = 0;
        dist[1][p[i]] = 0;
    }
    while (!pq.empty()) {
        auto N = pq.top(); pq.pop();
        ll u = N.s, t = -N.f;
        /**
         * Propogate every time there
         * is a new best second best
         * for a node.
        */
        for (auto [v, w] : adj[u]) {
            if (dist[1][u] + w < dist[0][v]) {
                if (dist[0][v] != dist[1][v]) {
                    pq.push({-dist[0][v], v});
                }
                swap(dist[0][v], dist[1][v]);
                dist[0][v] = dist[1][u] + w;
            } else if (dist[1][u] + w < dist[1][v]) {
                dist[1][v] = dist[1][u] + w;
                pq.push({-dist[1][v], v});
            }
        }
    }
    return (int) dist[1][0];
}

Compilation message

crocodile.cpp: In function 'int travel_plan(int, int, int (*)[2], int*, int, int*)':
crocodile.cpp:42:19: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   42 |         for (auto [v, w] : adj[u]) {
      |                   ^
crocodile.cpp:36:21: warning: unused variable 't' [-Wunused-variable]
   36 |         ll u = N.s, t = -N.f;
      |                     ^

Subtask #1
0 / 46.0

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

Subtask #2
0 / 43.0

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

Subtask #3
0 / 11.0

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