oj.uz

Submission #745796

# Submission time Handle Problem Language Result Execution time Memory
745796 2023-05-21T07:58:07 Z vjudge1 Cities (BOI16_cities) C++14
0 / 100
 230 ms 12936 KB 
#include <bits/stdc++.h>

using namespace std;
#define int long long

signed main(){

    int n, k, m;
    cin >> n >> k >> m;

    vector<vector<pair<int, int> > > graph(n);
    vector<int> important(k);

    for (int & x : important) cin >> x, x--;

    for (int i = 0; i < m; i++){
        int a, b, c;
        cin >> a >> b >> c;

        a--, b--;
        graph[a].push_back(make_pair(c, b));
        graph[b].push_back(make_pair(c, a));
    }

    // cout << important.size() << endl;
    // for (int x : important) cout << x << " ";
    // cout << endl;

    // cout << 1 << endl;

    long long tenyMo = LONG_LONG_MAX;
    for (int mask = 1; mask < (1 << n); mask++){
        
        bool jo = true;
        for (int x : important){
            if (!((1 << x) & mask)) {
                
                jo = false;

            }
        }
        if (!jo) continue;

        // cout << mask << endl;

        vector<int> minDist(n, INT_MAX);
        minDist[important.back()] = 0;
        vector<bool> vis(n, false);
        int visCnt = 0;
        long long mo = 0;

        priority_queue<pair<int, int> > q;
        q.push(make_pair(0, important.back()));
        while (!q.empty()){
            int pos = q.top().second, val = -q.top().first;
            q.pop();
            if (vis[pos]) continue;
            mo = mo + val;
            vis[pos] = true;
            visCnt++;
            for (pair<int, int> x : graph[pos]){
                if (vis[x.second] == false && minDist[x.second] > x.first){
                    minDist[x.second] = x.first;
                    q.push(make_pair(-x.first, x.second));
                }
            }
        }
        jo = true;
        for (int x : important){
            if (vis[x] == false) {
                
                jo = false;

            }
        }
        if (!jo) continue;
        tenyMo = min(tenyMo, mo);
    }
    cout << tenyMo << endl;

    return 0;
}

/*

6 3 6
1 2 3
1 2 3
1 3 3
1 4 2
2 3 3 
2 4 2
3 4 2

4 2 5
1 3
1 2 2
1 4 5
2 3 3
2 4 1
3 4 1


*/

Subtask #1
0 / 22.0

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

Subtask #2
0 / 14.0

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

Subtask #3
0 / 15.0

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

Subtask #4
0 / 23.0

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

Subtask #5
0 / 26.0

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