oj.uz

Submission #951312

# Submission time Handle Problem Language Result Execution time Memory
951312 2024-03-21T15:19:54 Z LucaIlie Cities (BOI16_cities) C++17
0 / 100
 354 ms 17416 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<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] } );
            }
        }
    }
}

bool inPerm[MAX_K];
vector<int> perm;
vector<vector<int>> perms;
void genperm( int p, int n ) {
    if ( p == n ) {
        perms.push_back( perm );
        return;
    }

    for ( int i = 0; i < n; i++ ) {
        if ( inPerm[i] )
            continue;

        inPerm[i] = true;
        perm.push_back( i );
        genperm( p + 1, n );
        perm.pop_back();
        inPerm[i] = false;
    }
}

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 minD = INF;
    for ( vector<int> perm: perms ) {
        for ( int v = 1; v <= n; v++ )
            vis[v] = false;
        
        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;
            }
        }
        minD = min( minD, d );
    }

    cout << minD;

    return 0;
}

Subtask #1
0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 10844 KB Output is correct
2 Correct 2 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 253 ms 17024 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0 / 15.0

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

Subtask #4
0 / 23.0

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

Subtask #5
0 / 26.0

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