oj.uz

답안 #723989

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
723989 2023-04-14T15:01:09 Z urosk 악어의 지하 도시 (IOI11_crocodile) C++14
0 / 100
 2 ms 2644 KB 
#include "crocodile.h"
#include <bits/stdc++.h>
#define dbg(x) cerr<<#x<<": "<<x<<endl;
#define ll long long
#define endl '\n'
#define pll pair<ll,ll>
#define fi first
#define sc second
#define pb push_back
#define llinf 1000000000LL
using namespace std;
#define maxn 100005

ll n,m,k;
vector<pll> g[maxn];
ll d[maxn][2];
bool ok[maxn];

int travel_plan(int N, int M, int R[][2], int L[], int K, int P[])
{
    n = N;
    m = M;
    k = K;
    for(ll i = 0;i<m;i++){
        ll x = R[i][0],y = R[i][1];
        x++; y++;
        ll w = L[i];
        g[x].pb({y,w});
        g[y].pb({x,w});
    }
    priority_queue<pll> pq;
    for(ll i = 1;i<=n;i++) d[i][0] = d[i][1] = llinf;
    for(ll i = 1;i<=k;i++){
        ll x = P[i-1] + 1;
        ok[x] = 1;
        d[x][0] = d[x][1] = 0;
        pq.push({0,x});
    }
    while(pq.size()){
        pll p = pq.top();
        pq.pop();
        ll u = p.sc;
        ll cur = -p.fi;
        if(cur>d[u][1]) continue;
        if(!ok[u]&&cur==d[u][0]) continue;
        for(pll p : g[u]){
            ll s = p.fi;
            ll w = p.sc;
            if(cur+w<d[s][0]){
                d[s][1] = d[s][1];
                d[s][0] = cur + w;
                pq.push({-d[s][0],s});
            }else if(cur+w<d[s][1]){
                d[s][1] = cur + w;
                pq.push({-d[s][1],s});
            }
        }
    }
    for(ll i = 1;i<=n;i++) cerr<<d[i][0]<< " "<<d[i][1]<<endl;
    return d[1][1];
}
/**
5 7 2
0 2 4
0 3 3
3 2 2
2 1 10
0 1 100
0 4 7
3 4 9
1 3
14


**/

Subtask #1
0 / 46.0

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

Subtask #2
0 / 43.0

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

Subtask #3
0 / 11.0

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