Submission #640647

#	Time	Username	Problem	Language	Result	Execution time	Memory
640647		makanhulia	Cities (BOI16_cities)	C++17	0 / 100	144 ms	11772 KiB

cities

#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 (stderr)

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