oj.uz

Submission #468252

# Submission time Handle Problem Language Result Execution time Memory
468252 2021-08-27T12:46:03 Z alextodoran Crocodile's Underground City (IOI11_crocodile) C++17
0 / 100
 0 ms 204 KB 
/**
 ____ ____ ____ ____ ____
||a |||t |||o |||d |||o ||
||__|||__|||__|||__|||__||
|/__\|/__\|/__\|/__\|/__\|

**/

#include <bits/stdc++.h>

#include "crocodile.h"

using namespace std;

typedef long long ll;

const ll INF = LLONG_MAX / 2;

struct Edge
{
    int to;
    ll len;
};

struct Path
{
    int to;
    ll len;
};

bool operator < (const Path &p1, const Path &p2)
{
    return p1.len > p2.len;
}

int travel_plan (int N, int M, int R[][2], int L[], int K, int P[])
{
    vector <vector <Edge>> adj (N);
    for(int i = 0; i < M; i++)
    {
        adj[R[i][0]].push_back(Edge{R[i][1], L[i]});
        adj[R[i][1]].push_back(Edge{R[i][0], L[i]});
    }

    vector <bool> visited (N, false);
    vector <ll> dist1 (N, INF);
    vector <ll> dist2 (N, INF);

    priority_queue <Path> q;

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

    while(q.empty() == false)
    {
        Path p = q.top();
        q.pop();

        if(visited[p.to] == true)
            break;

        visited[p.to] = true;

        for(Edge e : adj[p.to])
            if(visited[e.to] == false)
            {
                if(dist2[p.to] + e.len <= dist1[e.to])
                {
                    dist2[e.to] = dist1[e.to];
                    dist1[e.to] = dist2[p.to] + e.len;
                }
                else if(dist2[p.to] + e.len < dist2[e.to])
                {
                    dist2[e.to] = dist2[p.to] + e.len;
                }

                if(dist2[e.to] != INF)
                    q.push(Path{e.to, dist2[e.to]});
            }
    }

    return dist2[0];
}

Subtask #1
0 / 46.0

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

Subtask #2
0 / 43.0

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

Subtask #3
0 / 11.0

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