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] ;
  30. vector<pair<ll,ll > >adj[MAXN] ;
  31. //**Struct**//
  32.  
  33. //**Function**//
  34. void resett() {
  35.  
  36.     for(ll i = 1 ; i <= n  ; i++ ) adj[i].resize(0);
  37. }
  38. void init() {
  39.     cin>>n>> m ;
  40.     for(ll i = 1 ; i <= m ; i ++ ) {
  41.         ll x, y, w;
  42.         cin>>x>> y>> w;
  43.         adj[x].push_back({y, w }) ;
  44.     }
  45. }
  46. ll dijkstra(ll st, ll d[] ) {
  47.     for(ll i = 0 ; i <= n  ; i ++ ) d[i] = INF  ;
  48.     priority_queue<pair<ll,ll>,vector<pair<ll,ll>>, greater<pair<ll,ll> > > pq ;
  49.     for(pair<ll,ll>  v : adj[st]){
  50.    if(d[v.fi] > v.se )     pq.push({d[v.fi] = v.se , v.fi   }) ;
  51.     }
  52.     while(!pq.empty()) {
  53.         pair<ll,ll> u = pq.top()  ;
  54.         pq.pop() ;
  55.         if(d[u.se] < u.fi) continue ;
  56.         if(u.se  == st ) return d[u.se] ;
  57.         for(pair<ll,ll>  v : adj[u.se]) {
  58.             if(d[v.fi] > d[u.se] + v.se ) {
  59.                 pq.push({d[v.fi] = d[u.se] + v.se, v.fi }) ;
  60.             }
  61.         }
  62.     }
  63.     return -1 ;
  64. }
  65. void solve() {
  66.     for(ll i = 1 ; i <= n ; i ++ )cout<< dijkstra(i,  d1) <<el ;
  67.  
  68. }
  69.  
  70. __ROOT__ {
  71. //     freopen(NAME".inp" , "r" , stdin);
  72. //     freopen(NAME".out" , "w", stdout) ;
  73.     fast;
  74.     ll t;
  75.     cin >> t;
  76.     while(t--  ) {
  77.         init();
  78.         solve();
  79.         resett() ;
  80.     }
  81. }
  82.  
Success #stdin #stdout 0.01s 5288KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
https://ideone.com/dRZmEq
language:
C++14 (gcc 8.3)
created:
12 hours 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!