oj.uz

Submission #386589

# Submission time Handle Problem Language Result Execution time Memory
386589 2021-04-07T03:30:31 Z Kepha Crocodile's Underground City (IOI11_crocodile) C++11
0 / 100
 3 ms 3436 KB 
// IOI 2011 crocodile
#include "crocodile.h"
#include <queue>
#include <vector>
#include <string.h>
#define MX 100000
using namespace std;

int N, M, K;
vector<pair<int, int> > edges[MX + 1];
int dist1[MX + 1], dist2[MX + 1];
bool visited[MX + 1];
priority_queue<pair<int, int> > q;

int travel_plan(int N, int M, int R[][2], int L[], int K, int P[])
{
	for (int i = 1; i <= M; i++) {
        int a = R[i][0], b = R[i][1], c = L[i];
        edges[a].push_back({b, c});
        edges[b].push_back({a, c});
    }

	memset(dist1, 0x3f, sizeof(dist1));
    memset(dist2, 0x3f, sizeof(dist2));

    for (int i = 1; i <= K; i++) {
        int x = P[i];
        dist1[x] = dist2[x] = 0;
        q.push({0, x});
    }

    while (q.size()) {
        int node = q.top().second;
        q.pop();

        if (visited[node]) continue;
        visited[node] = true;

        for (auto& edge : edges[node]) {
            if (dist2[node] + edge.second < dist1[edge.first]) {
                dist2[edge.first] = dist1[edge.first];
                dist1[edge.first] = dist2[node] + edge.second;
                q.push({-dist2[edge.first], edge.first});
            }
            else if (dist2[node] + edge.second < dist2[edge.first]) {
                dist2[edge.first] = dist2[node] + edge.second;
                q.push({-dist2[edge.first], edge.first});
            }
        }
    }

  	return dist2[0];
}

Subtask #1
0 / 46.0

# Verdict Execution time Memory Grader output
1 Incorrect 3 ms 3436 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
0 / 43.0

# Verdict Execution time Memory Grader output
1 Incorrect 3 ms 3436 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0 / 11.0

# Verdict Execution time Memory Grader output
1 Incorrect 3 ms 3436 KB Output isn't correct
2 Halted 0 ms 0 KB -