Submission #788435

#	Time	Username	Problem	Language	Result	Execution time	Memory
788435		acatmeowmeow	Crocodile's Underground City (IOI11_crocodile)	C++11	0 / 100	1 ms	340 KiB

crocodile

#include "crocodile.h"
#include <bits/stdc++.h>

using namespace std;

const int NMAX = 1e3;
long long dist[NMAX + 5];
int par[NMAX + 5];
bool sink[NMAX + 5];
vector<pair<int, int>> adj[NMAX + 5];
priority_queue<pair<long long, int>, vector<pair<long long, int>>, greater<pair<long long, int>>> pq;

int travel_plan(int N, int M, int R[][2], int L[], int K, int P[]){

    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    for (int i = 0; i < M; i++) {
        adj[R[i][0]].push_back({R[i][1], L[i]});
        adj[R[i][1]].push_back({R[i][0], L[i]});
    }

    for (int i = 0; i < K; i++) sink[P[i]] = true;

    int curVertex = 0, ans = 0, prevU = -1;
    while (true) {
        //cout << curVertex << endl;
        if (sink[curVertex]) break;
        for (int i = 0; i < N; i++) dist[i] = 1e18, par[i] = -1;
        dist[curVertex] = 0;
        pq.push({0, curVertex});
        while (pq.size()) {
            int p = pq.top().first, u = pq.top().second; pq.pop();
            if (p != dist[u] || sink[u]) continue;
            if (u != curVertex && adj[u].size() <= 2) continue;
            for (auto&x : adj[u]) {
                int v = x.first;
                long long c = x.second;
                if (dist[v] < dist[u] + c) continue;
                if (u == curVertex && v == prevU) continue;
                dist[v] = dist[u] + c, par[v] = u;
                pq.push({dist[v], v});
            }
        }
        int f = -1, index = -1;
        long long fValue = 1e18, indexValue = 1e18;
        for (int i = 0; i < K; i++) {
            if (dist[P[i]] == 1e18) continue;
            //cout << dist[P[i]] << " ";
            if (dist[P[i]] < fValue) indexValue = fValue, index = f, fValue = dist[P[i]], f = P[i];
            else if (dist[P[i]] < indexValue) indexValue = dist[P[i]], index = P[i];
        }
        int u = index, nextU = 0;
        //cout << "U" << " " << u << endl;
        while (u != curVertex) nextU = u, u = par[u];
        for (auto&x : adj[u]) {
            int v = x.first, c = x.second;
            if (v == nextU) {
                ans += c;
                break;
            }
        }
        prevU = curVertex, curVertex = nextU;
        //if (nextU == 0) break;
    }
    return (int)ans;
}

/*#define MAX_N 50000
#define MAX_M 10000000

static int N, M;
static int R[MAX_M][2];
static int L[MAX_M];
static int K;
static int P[MAX_N];
static int solution;

inline
void my_assert(int e) {if (!e) abort();}

void read_input()
{
  int i;
  //my_assert(3==scanf("%d %d %d",&N,&M,&K));
  cin >> N>> M >> K;
  for(i=0; i<M; i++)
    //my_assert(3==scanf("%d %d %d",&R[i][0],&R[i][1],&L[i]));
    cin >> R[i][0] >> R[i][1] >> L[i];
  for(i=0; i<K; i++)
    //my_assert(1==scanf("%d",&P[i]));
    cin >> P[i];
  //my_assert(1==scanf("%d",&solution));
}

int main()
{
  int ans;
  read_input();
  ans = travel_plan(N,M,R,L,K,P);
cout << ans << '\n';

  return 0;
}*/

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