Join Us
Loading Similar Posts
Entering edit mode
The constraints for the first question are relaxed enough for us to just run a Dijkstra for all the warehouses:
```
#include <bits/stdc++.h>
#define ll long long
#define IOS ios_base::sync_with_stdio(false);cin.tie(NULL)
using namespace std;
#define MOD 1e9 + 7
using pii = pair<ll, ll>;
vector<ll> dijkstra (vector<pii> adj[], ll src, ll n) {
vector<ll> dist(n, INT_MAX);
priority_queue<pii, vector<pii>, greater<pii>> pq;
pq.push({src, 0});
dist[src] = 0;
while (!pq.empty()) {
ll v = pq.top().first, d_v = pq.top().second;
pq.pop();
if (d_v > dist[v]) continue;
for (auto nbr : adj[v]) {
ll node = nbr.first, node_dist = nbr.second;
if (dist[node] > dist[v] + node_dist) {
dist[node] = dist[v] + node_dist;
pq.push({node, dist[node]});
}
}
}
return dist;
}
int main() {
IOS;
ll tt = 1;
// cin >> tt;
while (tt--) {
ll n, k, ans = INT_MAX; cin >> n >> k;
vector<ll> outlets(k, 0);
for (auto& val : outlets) cin >> val;
set<ll> s;
for (auto val : outlets) s.insert(val);
ll m; cin >> m;
vector<pii> adj[m];
for (ll itr = 0; itr < m; itr++) {
ll u, v, dist; cin >> u >> v >> dist;
adj[u].push_back({v, dist});
adj[v].push_back({u, dist});
}
for (auto& val : outlets) {
auto dist = dijkstra(adj, val, n);
for (ll itr = 0; itr < n; itr++) {
if (itr != val && s.find(itr) != s.end()) ans = min(ans, dist[itr]);
}
}
cout << ans << '\n';
}
return 0;
}
```
```
