oj.uz

답안 #860233

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
860233 2023-10-12T09:25:00 Z phongcd 악어의 지하 도시 (IOI11_crocodile) C++14
0 / 100
 2 ms 6748 KB 
#include <bits/stdc++.h>
#define ll long long
#define ld long  double
#define ull unsigned long long
#define ii pair <int, int>
#define ill pair <ll, ll>
#define ild pair <ld, ld>
#define fi first
#define se second
#define all(x) x.begin(), x.end()
#define file "test"
using namespace std;
const int N = 1e5 + 2;
const int M = 10;
const ll MOD = 1e9 + 7;
const ll INF = 1e18;
const ll base = 311;
const int BLOCK_SIZE = 400;
 
int n, m, k;
vector <ill> g[N];

ll travel_plan (int nn, int mm, int r[][2], int l[], int kk, int p[]){
    n = nn, mm = m, k = kk;

    for (int i = 0; i < m; i ++) {
        ll u = r[i][0], v = r[i][1], w = l[i];
        g[u].push_back({v, w});
        g[v].push_back({u, w});
    }

    vector <ill> d(n);
    for (int i = 0; i < n; i ++) d[i] = {INF, INF};

    set <ill> h; 
    for (int i = 0, u; i < k; i ++) {
        u = p[i];
        h.insert({0, u});
        d[u] = {0, 0};
    }

    vector <bool> vis(n);
    while (!h.empty()) {
        int u = (*h.begin()).se;
        ll dis = (*h.begin()).fi;
        h.erase(h.begin());
        
        if (vis[u]) continue;
        vis[u] = 1;

        for (ill e: g[u]) {
            int v = e.fi; ll w = e.se;
            if (d[v].fi > dis + w) {
                d[v] = {dis + w, d[v].fi};
                h.insert({d[v].se, v});
            }
            else if (d[v].se > dis + w) {
                d[v].se = dis + w;
                h.insert({d[v].se, v});
            }
        }
    }

    return d[0].se;
}
/*
     /\_/\ zzZ
    (= -_-)
    / >u  >u
*/

Subtask #1
0 / 46.0

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

Subtask #2
0 / 43.0

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

Subtask #3
0 / 11.0

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