제출 #237246

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
237246		nicolaalexandra	악어의 지하 도시 (IOI11_crocodile)	C++14	46 / 100	171 ms	262148 KiB

crocodile

#include <bits/stdc++.h>
#include "crocodile.h"
#define DIMN 100010
#define DIMM 1000010
#define INF 2000000000
using namespace std;

vector <pair<int,int> > L[DIMN];
map <pair<int,int>, int> cost;
int f[DIMN],dp[DIMN];

void dfs (int nod, int tata){

    for (auto it : L[nod]){
        int vecin = it.first;
        if (vecin != tata)
            dfs (vecin,nod);
    }

    if (f[nod]){ /// e nod special
        dp[nod] = 0;
    } else {

        int mini = INF, mini2 = INF;
        for (auto it : L[nod]){
            int vecin = it.first, cost = it.second;
            if (vecin == tata)
                continue;
            if (dp[vecin] + cost < mini)
                mini2 = mini, mini = dp[vecin] + cost;
            else {
                if (dp[vecin] + cost < mini2)
                    mini2 = dp[vecin] + cost;
            }
        }

        if (mini2 != INF)
            dp[nod] = mini2;
        else dp[nod] = mini;

    }

}

int travel_plan (int n, int m, int r[][2], int l[], int k, int p[]){
    int i;

    for (i=0;i<m;i++){
        int x = r[i][0]+1, y = r[i][1]+1;
        L[x].push_back(make_pair(y,l[i]));
        L[y].push_back(make_pair(x,l[i]));
        cost[make_pair(x,y)] = l[i];
        cost[make_pair(y,x)] = l[i];
    }

    for (i=0;i<k;i++){
        int x = p[i] + 1;
        f[x] = 1;
    }

    dfs (1,0);

    return dp[1];

}

• Subtask 1: 46 / 46
• Subtask 2: 0 / 43
• Subtask 3: 0 / 11