oj.uz

Submission #951308

# Submission time Handle Problem Language Result Execution time Memory
951308 2024-03-21T15:16:25 Z LucaIlie Cities (BOI16_cities) C++17
0 / 100
 333 ms 21520 KB 
#include <bits/stdc++.h>

using namespace std;

const int MAX_N = 1e5;
const int MAX_M = 2e5;
const int MAX_K = 5;
const long long INF = 1e15;

struct edge {
    int u, v, c;

    int other( int x ) {
        return u ^ v ^ x;
    }
};

struct dv {
    int v;
    long long d;

    bool operator < ( const dv &x ) const {
        return d > x.d;
    }
};

int cities[MAX_K];
vector<vector<int>> perms;
vector<int> adj[MAX_N + 1];
edge edges[MAX_M];
bool vis[MAX_N + 1];
long long dist[MAX_K][MAX_N + 1];
int parent[MAX_K][MAX_N + 1];

void dijkstra( int s, long long dist[], int parent[] ) {
    priority_queue<dv> pq;

    for ( int v = 0; v <= MAX_N; v++ )
        dist[v] = INF;

    dist[s] = 0;
    parent[s] = 0;
    pq.push( { s, dist[s] } );
    while ( !pq.empty() ) {
        int u = pq.top().v;
        int d = pq.top().d;
        pq.pop();

        if ( d > dist[u] )
            continue;

        for ( int e: adj[u] ) {
            int v = edges[e].other( u );

            if ( dist[u] + edges[e].c < dist[v] ) {
                dist[v] = dist[u] + edges[e].c;
                parent[v] = u;
                pq.push( { v, dist[v] } );
            }
        }
    }
}

int main() {
    int n, k, m;

    cin >> n >> k >> m;

    //genperm( 0, k );

    for ( int i = 0; i < k; i++ )
        cin >> cities[i];

    for ( int i = 0; i < m; i++ ) {
        cin >> edges[i].u >> edges[i].v >> edges[i].c;
        adj[edges[i].u].push_back( i );
        adj[edges[i].v].push_back( i );
    }

    for ( int i = 0; i < k; i++ )
        dijkstra( cities[i], dist[i], parent[i] );

    long long d = 0;
    vis[cities[0]] = true;
    for ( int i = 1; i < k; i++ ) {
        int u = 0;
        for ( int v = 1; v <= n; v++ ) {
            if ( vis[v] && dist[i][v] < dist[i][u] )
                u = v;
        }
        d += dist[i][u];

        int c = cities[i];
        while ( u != c ) {
            u = parent[i][u];
            vis[u] = true;
        }
    }

    cout << d;

    return 0;
}

Subtask #1
0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 10844 KB Output is correct
2 Correct 4 ms 10844 KB Output is correct
3 Incorrect 2 ms 10844 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #2
0 / 14.0

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

Subtask #3
0 / 15.0

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

Subtask #4
0 / 23.0

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

Subtask #5
0 / 26.0

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