CSES – Shortest Routes II

#include<bits/stdc++.h>
#define int long long
#define pii pair<int,int>
#define f first
#define s second
#define fastio ios_base::sync_with_stdio(0);cin.tie(0)
using namespace std;
//declare
const int maxn = 505;
int n,m,q,dis[maxn][maxn];
//
void floyd_warshell(){
    for(int k=1;k<=n;k++){
        for(int i=1;i<=n;i++){
            for(int j=1;j<=n;j++){
                dis[i][j] = min(dis[i][j], dis[i][k] + dis[k][j]);
            }
        }
    }
}
signed main(){
    fastio;
    cin>>n>>m>>q;
    for(int i=1;i<=n;i++){
        for(int j=1;j<=n;j++){
            if(i == j) dis[i][j] = 0;
            else dis[i][j] = 1e18;
        }
    }
    for(int i=0;i<m;i++){
        int a,b,c; cin>>a>>b>>c;
        dis[a][b] = dis[b][a] = min(dis[a][b],c);
    }
    floyd_warshell();
    while(q--){
        int a,b; cin>>a>>b;
        cout<<(dis[a][b] == 1e18 ? -1 : dis[a][b])<<"\n";
    }
    return 0;
}