# Untitled

unknown
c_cpp
14 days ago
2.5 kB
17
Indexable
Never
```#include <bits/stdc++.h>
using namespace std;
typedef long long int ll;
typedef long double ld;
#define fo(i, n) for (i = 0; i < n; i++)
#define pb push_back
#define all(v) v.begin(),v.end()
#define m_p make_pair
const ll mod=1e9+7;
#define INF LLONG_MAX
//---------------------------------------------------------------------------------------------

//---------------------------------------------------------------------------------------------
void greninja(vector<vector<pair<ll,ll>>> &graph, ll sz , ll src , vector<ll>& dist) {

priority_queue<pair<ll, ll>, vector<pair<ll, ll>>, greater<pair<ll, ll>>> pq;
for(auto &x:dist)
x = INF;
pq.push({0, src});
dist[src] = 0;

while (!pq.empty()) {
ll u = pq.top().second;
ll current_dist = pq.top().first;
pq.pop();

// Prune the node if the current distance is not better
if (current_dist > dist[u]) {
continue;
}

for (auto &x : graph[u]) {
ll v = x.first;
ll weight = x.second;

if (dist[v] > dist[u] + weight) {
dist[v] = dist[u] + weight;
pq.push({dist[v], v});
}
}
}
}
//---------------------------------------------------------------------------------------------
void solve()
{
ll n , m , q;
cin >> n >> m >> q;
vector<vector<pair<ll,ll>>> graph(n + 1);
ll i;
fo(i,m)
{
ll a , b , c;
cin >> a >> b >> c;
graph[a].pb({b , c});
graph[b].pb({a , c});
}
vector<ll> dist(n + 1);
ll ans[n + 1][n + 1];
for(i = 1 ; i <= n ; i++)
{
greninja(graph , n + 1 , i , dist);
for(ll j = 1 ; j <= n ; j++)
ans[i][j] = dist[j];
}
while(q--)
{
ll a , b;
cin >> a >> b;
if(ans[a][b] == INF)
cout << -1;
else
cout << ans[a][b];
cout << "\n";
}
}
//---------------------------------------------------------------------------------------------
int main()
{
//BINARY SEARCH ON ANS
//DISJOINT SET UNION
//INVERSE MODULO
ios_base::sync_with_stdio(false);
cin.tie(0);cout.tie(0);
ll t;
// cin>>t;
t=1;
while(t--)
{
solve();
}
}
//---------------------------------------------------------------------------------------------```