oj.uz

답안 #460545

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
460545 2021-08-09T07:31:12 Z BT21tata 악어의 지하 도시 (IOI11_crocodile) C++17
0 / 100
 2 ms 3404 KB 
#include<bits/stdc++.h>
#include "crocodile.h"
typedef long long ll;

using namespace std;

vector<pair<ll,ll> >g[100005];
priority_queue<pair<ll,ll> >q;
ll dis[100005], ans;
bool used[100005], ext[100005];

ll check(int v)
{
    if(ext[v]) return -1;
    ll mx=0, cnt=0;
    for(pair<ll, ll> u : g[v])
    {
        if(ext[u.first]) cnt++, mx=max(mx, dis[u.first]); 
    }
    if(cnt<2) return -1;
    return mx;
}

int travel_plan(int n, int m, int R[][2], int L[], int k, int P[])
{
    memset(dis, 63, sizeof(dis));
    for(int i=0; i<m; i++)
    {
        g[R[i][0]].push_back({R[i][1], L[i]});
        g[R[i][1]].push_back({R[i][0], L[i]});
    }
    for(int i=0; i<k; i++)
        ext[P[i]]=1;
    q.push({0, 0});
    dis[0]=0;
    while(!q.empty())
    {
        int s=q.top().second;
        q.pop();
        if(used[s]) continue;
        used[s]=1;
        for(pair<ll, ll> u : g[s])
        {
            if(dis[s]+u.second<dis[u.first])
            {
                dis[u.first]=dis[s]+u.second;
                q.push({-dis[u.first], u.first});   
            }
        }
    }

    for(int i=0; i<n; i++)
    {
        ans=max(ans, check(i));
    }
    return ans;
}


/*
5 4 3
0 1 2
0 2 3
3 2 1
2 4 4
1 3 4
7

*/

Subtask #1
0 / 46.0

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

Subtask #2
0 / 43.0

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

Subtask #3
0 / 11.0

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