oj.uz

답안 #876664

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
876664 2023-11-22T07:50:24 Z deadeye0 악어의 지하 도시 (IOI11_crocodile) C++17
0 / 100
 1 ms 4700 KB 
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
#define fi first
#define si second
#define ar array
#define pb push_back
typedef pair<ll,int> pi;
typedef tuple<int,int,int> ti;  
typedef vector<int> vi;
template<typename T> bool chmin(T &a, T b){return (b < a) ? a = b, 1 : 0;}
template<typename T> bool chmax(T &a, T b){return (b > a) ? a = b, 1 : 0;}
void debug_out() {cerr<<endl;}
template <typename Head, typename... Tail>
void debug_out(Head _H, Tail... _T) {cerr<<" "<<to_string(_H);debug_out(_T...);}
#define debug(...) cerr<<"["<<#__VA_ARGS__<<"]:",debug_out(__VA_ARGS__)
const int MAXN = 100010;
int n, m;
int par[MAXN];
ll d1[MAXN], d2[MAXN], ans = 1e18;
vector<vector<pi>> g;
priority_queue<pi, vector<pi>, greater<pi>> pq;

int travel_plan(int N, int M, int R[][2], int L[], int K, int P[]) 
{
    n = N, m = M;
    g.resize(n);
    for (int i = 0; i < m; ++i) {
        int u = R[i][0], v = R[i][1];
        g[u].pb({v, L[i]});
        g[v].pb({u, L[i]});
    }
    memset(d1, -1, sizeof d1);
    memset(par, -1, sizeof par);
    for (int i = 0; i < K; ++i)  {
        d1[P[i]] = 0;
        pq.push({0, P[i]});
    }   
    while (pq.size()) {
        auto [d, x] = pq.top(); pq.pop();
        if (d1[x] != d) continue;
        for (auto i: g[x]) {
            ll val = d + i.si;
            if (d1[i.fi] == -1 || d1[i.fi] > val) {
                d1[i.fi] = val;
                par[i.fi] = x;
                pq.push({val, i.fi});
            }
        }
    }
    memset(d2, -1, sizeof d2);
    d2[0] = 0;
    pq.push({0, 0});
    while (pq.size()) {
        auto [d, x] = pq.top(); pq.pop();
        if (d2[x] != d) continue;
        for (auto i: g[x]) {
            if (par[x] == i.fi) continue;
            ll val = d + i.si;
            if (d2[i.fi] == -1 || d2[i.fi] > val) {
                d2[i.fi] = val;
                pq.push({val, i.fi});
            }
        }
    }
    for (int i = 0; i < K; ++i) {
        if (d2[P[i]] == -1) continue;
        chmin(ans, d2[P[i]]);
    }
    return ans;
}

Subtask #1
0 / 46.0

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

Subtask #2
0 / 43.0

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

Subtask #3
0 / 11.0

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