fork download
copy 
  1. // ROOT : DRAGON3012009
  2. #include <bits/stdc++.h>
  3. #define ll int
  4. #define el "\n"
  5. #define fast ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
  6. #define __ROOT__ int main()
  7. #pragma GCC optimize("O2")
  8. #pragma GCC target("avx,avx2,fma")
  9. #define fi first
  10. #define se second
  11. #define M 1000000007
  12. #define MAXN 1001
  13. #define GIOIHAN 1000001
  14. #define BLOCK_SIZE 425
  15. #define MAX_NODE 1001001
  16. #define LOG 19
  17. #define ALPHA_SIZE 26
  18. #define BASE 311
  19. #define NAME "file"
  20. #define INF 1e8
  21. #define compare(v) sort((v).begin(), (v).end()); (v).erase(unique((v).begin(), (v).end()), (v).end()); // dùng để nén sort mảng compare
  22. using namespace std;
  23. const ll MOD[] = {(ll)1e9 + 2277, (ll)1e9 + 5277, (ll)1e9 + 8277, (ll)1e9 + 9277, (ll) 1e9 + 7 };
  24. const ll NMOD = 1;
  25. const int dx[] = {-1, 0, 1,0};
  26. const int dy[] = {0, 1, 0, -1};
  27. //**Variable**//
  28. ll n,  m   ;
  29. ll d1[MAXN][MAXN] ;
  30. vector<pair<ll,ll > >adj[MAXN] ;
  31. //**Struct**//
  32.  
  33. //**Function**//
  34. void resett() {
  35.     for(ll i = 0 ; i <= n  ; i ++ ) {
  36.         for(ll j  = 0 ; j <= n ; j ++ ) d1[i][j] = INF ;
  37.     }
  38.     for(ll i = 1 ; i <= n  ; i++ ) adj[i].resize(0);
  39. }
  40. void init() {
  41.     cin>>n>> m ;
  42.     for(ll i = 1 ; i <= m ; i ++ ) {
  43.         ll x, y, w;
  44.         cin>>x>> y>> w;
  45.         adj[x].push_back({y, w }) ;
  46.     }
  47. }
  48. void dijkstra(ll st, ll d[] ) {
  49.     d[st] = 0 ;
  50.     priority_queue<pair<ll,ll>,vector<pair<ll,ll>>, greater<pair<ll,ll> > > pq ;
  51.     pq.push({0, st }) ;
  52.     while(!pq.empty()) {
  53.         pair<ll,ll> u = pq.top()  ;
  54.         pq.pop() ;
  55.         if(d[u.se] < u.fi) continue ;
  56.         for(pair<ll,ll>  v : adj[u.se]) {
  57.             if(d[v.fi] > d[u.se] + v.se ) {
  58.                 pq.push({d[v.fi] = d[u.se] + v.se, v.fi }) ;
  59.             }
  60.         }
  61.     }
  62. }
  63. void solve() {
  64.     for(ll i = 1 ; i <= n ; i ++ ) dijkstra(i,  d1[i]) ;
  65.     for(ll i = 1 ; i <= n ; i ++ ) {
  66.         ll ans = INF ;
  67.         for(ll j = 1 ; j <= n ; j ++ ) {
  68.             if(i == j)  continue ;
  69. //            cout<<d1[i][j] <<" " << d1[j][i] <<el ;
  70.             ans = min(d1[i][j] + d1[j][i], ans ) ;
  71.         }
  72.         cout<<(ans == INF ? -1 : ans ) << el ;
  73.     }
  74. }
  75.  
  76. __ROOT__ {
  77. //     freopen(NAME".inp" , "r" , stdin);
  78. //     freopen(NAME".out" , "w", stdout) ;
  79.     fast;
  80.     ll t;
  81.     cin >> t;
  82.      for(ll i = 0 ; i < MAXN  ; i ++ ) {
  83.         for(ll j  = 0 ; j < MAXN  ; j ++ ) d1[i][j] = INF ;
  84.     }
  85.     while(t--  ) {
  86.         init();
  87.         solve();
  88.         resett() ;
  89.     }
  90. }
  91.  
Success #stdin #stdout 0.01s 7424KB
comments (?)
stdin
copy 
1
6 8
1 2 4
2 4 2
4 3 3
3 1 4
4 1 5
3 5 5
5 3 1
5 6 7
stdout
copy 
11
11
6
11
6
-1
https://ideone.com/jV0pqV
language:
C++14 (gcc 8.3)
created:
245 days ago
visibility:
secret

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!