제출 #951308

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
951308		LucaIlie	Cities (BOI16_cities)	C++17	0 / 100	333 ms	21520 KiB

cities

#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
• Subtask 2: 0 / 14
• Subtask 3: 0 / 15
• Subtask 4: 0 / 23
• Subtask 5: 0 / 26