oj.uz

Submission #641960

# Submission time Handle Problem Language Result Execution time Memory
641960 2022-09-18T03:38:13 Z devariaota Cities (BOI16_cities) C++17
0 / 100
 6000 ms 29160 KB 
#include <bits/stdc++.h>

#define mp make_pair
#define int long long
#define pb push_back
#define STC stack <int>
#define pii pair <int, int>
#define vi vector <int>
#define vii vector <vi >
#define se second
#define fi first

using namespace std;
const int mod = 1e9 + 7;
const int MxN = 1e9 + 7;

signed main(){

  ios_base::sync_with_stdio(false);
  cout.tie(0);
  cin.tie(NULL);

  int n, k, m; cin >> n >> k >> m;
  vi P(k);
  vector <vector <pii>> N(n + 1);
  for(int i = 0; i < k; i++) cin >> P[i];
  for(int i = 0; i < m; i++){
    int a, b, c; cin >> a >> b >> c;
    N[a].pb({b, c});
    N[b].pb({a, c});
  }  

  int ans = LLONG_MAX;
  for(int i = 1; i <= n; i++){
    priority_queue <pair <pii, pii>, vector <pair <pii, pii>>, greater <pair <pii, pii>>> Q;
    Q.push({{0, 0}, {i, i}});
    vi V(n+1, 1e18);
    vector <pii> par(n + 1, {-1, -1});
    par[i] = {i, 0};
    while(Q.size()){
      int val = Q.top().fi.fi, preVal = Q.top().fi.se, cur = Q.top().se.fi, prev = Q.top().se.se;
      Q.pop();

      if(V[cur] < val) continue;
      V[cur] = val;
      par[cur] = {prev, preVal};

      for(auto it : N[cur]){
        Q.push({{val + it.se, it.se}, {it.fi, cur}});
      }
    }

    vi Va(n + 1, 0);
    queue <int> A;
    int sum = 0;
    for(int j = 0; j < k; j++){
      A.push(par[P[j]].fi);
      sum += par[P[j]].se;
      Va[P[j]] = 1;
    }

    while(A.size()){
      int cur = A.front();
      A.pop();

      if(Va[cur] == 1) continue;
      Va[cur] = 1;
      sum += par[cur].se;
      A.push(par[cur].fi);
    }

    ans = min(ans, sum);
  }
  cout << ans << "\n";
}

Subtask #1
0 / 22.0

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

Subtask #2
0 / 14.0

# Verdict Execution time Memory Grader output
1 Execution timed out 6049 ms 28992 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #3
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 465 ms 576 KB Output is correct
2 Incorrect 427 ms 612 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #4
0 / 23.0

# Verdict Execution time Memory Grader output
1 Execution timed out 6054 ms 28912 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #5
0 / 26.0

# Verdict Execution time Memory Grader output
1 Execution timed out 6057 ms 29160 KB Time limit exceeded
2 Halted 0 ms 0 KB -