fork download 
  1. #include<bits/stdc++.h>
  2. #define FIO ios_base::sync_with_stdio(0);cin.tie(0);
  3. using namespace std;
  4. typedef long long ll;
  5.  
  6. const int MOD=1e9+7, OO=0x3f3f3f3f;
  7. const ll LOO=0x3f3f3f3f3f3f3f3f;
  8. const long double EPS=1e-8;
  9.  
  10.  
  11.  
  12. void floyd(vector<vector<int>>& dis){
  13.   int n=dis.size();
  14.   for(int k=0; k<n; k++)
  15.     for(int u=0; u<n; u++)
  16.       for(int v=0; v<n; v++)
  17.         dis[u][v]=min(dis[u][v], dis[u][k] + dis[k][v]);
  18. }
  19.  
  20. int main(){
  21.   FIO 
  22.   // freopen("input.txt","rt",stdin);
  23.   // freopen("output.txt","wt",stdout);
  24.   int t,tc=0;
  25.   cin>>t;
  26.   while(t--){
  27.     int n;
  28.     cin>>n;
  29.     vector<vector<int>>dis(n, vector<int>(n));
  30.     for(auto& v : dis)
  31.       for(auto& x : v)
  32.         cin>>x;
  33.     floyd(dis);
  34.     int q;
  35.     cin>>q;
  36.     ll ans=0;
  37.     while(q--){
  38.       int src, tar;
  39.       cin>>src>>tar;
  40.       ans+=dis[src-1][tar-1];
  41.     }
  42.     cout<<"Case #"<<++tc<<": "<<ans<<'\n';
  43.   }
  44.  
  45.   return 0;
  46. } 
  47.  
  48.  
Success #stdin #stdout 0.01s 5432KB
comments (?)
stdin 
1
3
0 1 1
1 0 1
1 9 0
2
2 1
3 2
stdout 
Case #1: 3
https://ideone.com/Skb7Nn
language:
C++14 (gcc 8.3)
created:
2 years ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!