Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include <bits/stdc++.h>
- using namespace std;
- typedef long long ll;
- const long long INF = 1e18;
- struct Routes{
- int from;
- int to;
- ll weight;
- };
- int n, m, q;
- Routes route[250001];
- vector<vector<ll>> dp;
- int main(){
- //freopen("routesII.in", "r", stdin);
- cin >> n >> m >> q;
- dp.resize(n+1, vector<ll>(n+1, INF));
- //for(int i=1; i<=n; i++){
- //for(int j=1; j<=n; j++){
- //dp[i][j] = LLONG_MAX;
- //}
- //}
- for(int i=0; i<m; i++){
- cin >> route[i].from >> route[i].to >> route[i].weight;
- //cout << route[i].from << ", " << route[i].to << ", " << route[i].weight << '\n';
- dp[route[i].from][route[i].to] = min(dp[route[i].from][route[i].to], route[i].weight);
- dp[route[i].to][route[i].from] = min(dp[route[i].to][route[i].from], route[i].weight);
- }
- //memset(dp, 1e9, sizeof(dp));
- //dp[1][1] = 1e9;
- for(int i=1; i<=n; i++){
- dp[i][i] = 0;
- }
- for(int k=1; k<=n; k++){
- for(int i=1; i<=n; i++){
- for(int j=1; j<=n; j++){
- dp[i][j] = min(dp[i][j], dp[i][k]+dp[k][j]);
- }
- }
- }
- //for(int i=1; i<=n; i++){
- //for(int j=1; j<=n; j++){
- //cout << dp[i][j] << " ";
- //}
- //cout << '\n';
- //}
- for(int i=0; i<q; i++){
- int a, b;
- cin >> a >> b;
- if(dp[a][b] == INF){
- cout << -1 << '\n';
- }else{
- cout << dp[a][b] << '\n';
- }
- }
- return 0;
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement
