CSES - Shared codeLink to this code:
https://cses.fi/paste/be6fbe24b86a1467986b2f/
#include <bits/stdc++.h>
#define pb push_back
using namespace std;
const int64_t INF = LLONG_MAX-1;
const int N = 500+10;
vector<vector<int64_t>> dist(N , vector<int64_t>(N , INF));
int64_t n,m,q;
void floydWarshall(){
int i, j, k;
for (k = 0; k <= n; k++) {
for (i = 0; i <= n; i++) {
for (j = 0; j <= n; j++) {
if (dist[i][j] > (dist[i][k] + dist[k][j]) && (dist[k][j] != INF && dist[i][k] != INF))
dist[i][j] = dist[i][k] + dist[k][j];
}
}
}
}
int main(){
cin.tie(0)->ios::sync_with_stdio(0);
cin>>n>>m>>q;
for(int64_t i=0;i<m;i++){
int64_t a,b,c;
cin>>a>>b>>c;
dist[a][b]=min(dist[a][b], c);
dist[b][a]=min(dist[b][a], c);
}
floydWarshall();
for(int64_t i=0;i<q;i++){
int64_t a,b;
cin>>a>>b;
if(a==b){
cout<<0<<'\n';
}else
cout<<((min(dist[b][a],dist[a][b])==INF)?-1:dist[a][b])<<'\n';
}
}