oj.uz

Submission #640647

# Submission time Handle Problem Language Result Execution time Memory
640647 2022-09-15T04:39:26 Z makanhulia Cities (BOI16_cities) C++17
0 / 100
 144 ms 11772 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 (!st.count(pq.top().sc))
  {
    auto [c, idx] = pq.top();
    pq.pop();

    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 = pq.top().sc;
  st.insert(now);
  while (pref[now] != -1)
  {
    st.insert(pref[now]);
    now = pref[now];
  }

  return pq.top().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;
}

Compilation message

cities.cpp: In function 'll dijkstra(int)':
cities.cpp:35:7: warning: variable 'ret' set but not used [-Wunused-but-set-variable]
   35 |   pll ret = {1e18, 0};
      |       ^~~

Subtask #1
0 / 22.0

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

Subtask #5
0 / 26.0

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