oj.uz

Submission #640648

# Submission time Handle Problem Language Result Execution time Memory
640648 2022-09-15T04:41:49 Z christinelynn Cities (BOI16_cities) C++17
0 / 100
 126 ms 11704 KB 
#include <bits/stdc++.h>
using namespace std;
#pragma GCC optimize("Ofast")
typedef long long ll;
// const ll mod = 1e9 + 7;
const ll MAXN = 1e5 + 5;
#define vi vector<int>
#define vll vector<ll>
#define pii pair<int, int>
#define pll pair<ll, ll>
#define mp make_pair
#define pb push_back
#define lb lower_bound
#define ub upper_bound
#define fi first
#define sc second
#define endl '\n'
#define gl                        ios_base::sync_with_stdio(0);   cin.tie(0);                     cout.tie(0)

vi im;
int n, m, k;
vector<pii> adj[MAXN];
set<int> st;
ll ans;

ll dijkstra(int i)
{
  priority_queue<pll, vector<pll>, greater<pll>> pq;
  vll dis(n + 1, 1e18);
  vi pref(n + 1, -1);

  dis[i] = 0;
  pq.push({0, i});

  pll ret = {1e18, 0};

  while (!pq.empty() and pq.top().fi <= ret.fi)
  {
    auto [c, idx] = pq.top();
    pq.pop();

    if (st.count(idx) and c < ret.fi)
      ret = {c, idx};

    for (pii v : adj[idx])
    {
      if (c + v.sc < dis[v.fi])
      {
        dis[v.fi] = c + v.sc;
        pref[v.fi] = idx;
        pq.push({c + v.sc, v.fi});
      }
    }
  }

  int now = ret.sc;
  st.insert(now);
  while (pref[now] != -1)
  {
    st.insert(pref[now]);
    now = pref[now];
  }
  // for (int i : st)
  //   cout << i << ' ';
  // cout << endl;

  return ret.fi;
}

int main()
{
  gl;
  cin >> n >> k >> m;

  for (int i = 0; i < k; i++)
  {
    int x;
    cin >> x;
    im.pb(x);
  }

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

  st.insert(im[0]);

  for (int i = 1; i < k; i++)
  {
    ans += dijkstra(im[i]);
  }

  cout << ans << endl;

  return 0;
}

Subtask #1
0 / 22.0

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

Subtask #2
0 / 14.0

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

Subtask #3
0 / 15.0

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

Subtask #4
0 / 23.0

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

Subtask #5
0 / 26.0

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