fork download
copy 
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3. #define endl "\n"
  4. #define int long long
  5. #define faster() ios::sync_with_stdio(false); cin.tie(nullptr); cout.tie(nullptr);
  6.  
  7. // do phuc tap (V^3) => ap dung cho V <= 400
  8. int Mat[1005][1005] , n , m ;
  9. void Floyd(){
  10.     for(int k = 1 ; k <= n ; k++){
  11.         for(int i = 1 ; i <= n ; i++){
  12.             for(int j = 1 ; j <= n ; j++){
  13.                 Mat[i][j] = min(Mat[i][j] , Mat[i][k] + Mat[k][j]);
  14.             }
  15.         }
  16.     }
  17. }
  18.  
  19. void solve(){
  20.     cin >> n >> m ;
  21.     for(int i = 1 ; i <= n ; i++){
  22.         for(int j = 1 ; j <= m ; j++){
  23.             if( i == j) Mat[i][j] = 0 ;
  24.             else Mat[i][j] = 1e9 ;
  25.         }
  26.     }
  27.     for(int i = 1 ; i <= m ; i++){
  28.         int x , y, w ; cin >> x >> y >> w ;
  29.         Mat[x][y] = Mat[y][x] = w ;
  30.     }
  31.  
  32.     Floyd();
  33.  
  34.     int q ; cin >> q ;
  35.     while(q--){
  36.         int u , v ; cin >> u >> v ;
  37.         cout << Mat[u][v] << endl;
  38.     }
  39. }
  40.  
  41. signed main() {
  42.     faster(); 
  43.     int test = 1 ; 
  44.     // cin >> test ;
  45.     while(test--)   solve();
  46.     return 0;
  47. }
  48.  
Success #stdin #stdout 0.01s 5284KB
comments (?)
stdin
copy 
5 6
1 2 6
1 3 7
2 4 8
3 4 9
3 5 1
4 5 2
3
1 5
2 5
4 3
stdout
copy 
8
10
3
https://ideone.com/JDK5f3
language:
C++ (gcc 8.3)
created:
6 days 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!