1433G - Reducing Delivery Cost - CodeForces Solution

#include <bits/stdc++.h>

using namespace std;

#define ll long long 
#define ld long double 
#define Raghad ios_base::sync_with_stdio(0), cin.tie(0), cout.tie(0);
#define pub push_back
#define pok pop_back
#define puf push_front
#define pof pop_front
#define fr first
#define se second
#define MOD 1000000007
#define nl "\n"
#define loop(j,n)  for(int i=j;i<n;i++)
#define mkp make_pair
#define big begin()
#define en end()
#define all(v) v.begin(),v.end()
#define is(f) if(f)cout <<"YES\n";else cout << "NO\n";

vector < vector <pair <ll, ll> >> adj;
map<ll, bool>vis;
vector < pair <ll, ll> > edge,r;
ll dist[1050][1050];
priority_queue < pair < ll , ll > , vector<pair<ll, ll>>, greater<pair<ll, ll> > > pq;

void initialize(ll n,ll m) {
	adj = vector < vector <pair <ll, ll> >>(n+1);

	loop(1, n + 1)
		for(int j=1;j<=n;j++)
			dist[i][j] = 1e12;

	ll x, y, w;
	loop(0, m) {
		cin >> x >> y >> w;
		edge.pub({ x, y });
		adj[x].pub({ y,w });
		adj[y].pub({ x,w });
	}

}
void dijkstra(ll s) {
	ll node, minVal,newDist;
	pq.push({ 0,s });
	dist[s][s] = 0;

	while (!pq.empty()) {
		node = pq.top().se;
		minVal = pq.top().fr;
		pq.pop();
		vis[node] = true;

		if (dist[s][node] < minVal)continue;

		for (auto child : adj[node]) {
			if (!vis[child.fr]) {
				newDist = dist[s][node] + child.second;
				if (newDist < dist[s][child.fr]) {
					dist[s][child.fr] = newDist;
					pq.push({ dist[s][child.fr],child.fr });
				}
				
			}
		}
	}

}

int main() {
	Raghad
    ll t = 1;
	//cin >> t;
	while (t--) {
		ll n, m, k,a,b,ans=1e12; cin >> n >> m >> k;
		initialize(n, m);
		
		loop(1,n+1)dijkstra(i),vis.clear();
		
		loop(0, k) {
			cin >> a >> b;
			r.pub({ a,b });
		}
		
		for (auto i : edge) {
			int x = i.fr, y = i.se, sum = 0;
			for (auto j : r) {
				int a = j.fr, b = j.se;
				sum += min<ll>({ dist[a][b], dist[a][x] + dist[y][b], dist[a][y] + dist[x][b] });
			}
			ans = min<ll>(ans, sum);
		}
		cout << ans;
	}
}