fork download
copy 
  1. // ROOT : DRAGON3012009
  2. #include <bits/stdc++.h>
  3. #define ll long long
  4. #define ld long double
  5. #define el "\n"
  6. #define fast ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
  7. #define __ROOT__ int main()
  8. #pragma GCC optimize("O2")
  9. //#pragma GCC optimize("unroll-loops")
  10. //#pragma GCC target("avx2,bmi,bmi2,popcnt,lzcnt")
  11. #define FOR(i,l,r) for(int i = l ; i <= r ; i ++)
  12. #define FORD(i,r,l) for(int i = r ; i >= l ; i --)
  13. #define REP(i, a ) for(int i = 0 ; i < a ; i ++ )
  14. #define fi first
  15. #define se second
  16. #define M 1000000007
  17. #define MAXN 3001
  18. #define INF (1ll<<60)
  19. #define BLOCK_SIZE 425
  20. #define MAX_NODE 1001001
  21. #define LOG 19
  22. #define ALPHA_SIZE 26
  23. #define BASE 256
  24. #define NAME "file"
  25. #define compare(v) sort((v).begin(), (v).end()); (v).erase(unique((v).begin(), (v).end()), (v).end());
  26. using namespace std;
  27. using namespace chrono ;
  28. const ll MOD[] = {(ll)1e9 + 2277, (ll)1e9 + 5277, (ll)1e9 + 8277, (ll)1e9 + 9277, (ll) 1e9 + 7 };
  29. const ll NMOD = 1;
  30. const int dx[] = {-1, 0, 1,0};
  31. const int dy[] = {0, 1, 0, -1};
  32. //**Variable**//
  33. ll n, m ;
  34. ll arr[MAXN];
  35. ll ma[MAXN][3] ;
  36. ll lab[MAXN] ;
  37. ll out[MAXN] ;
  38. ll d[MAXN] ;
  39. ll min_res = INF ;
  40.  vector<ll > S_edge ;
  41. vector<ll > res;
  42. vector<pair<ll,ll> > adj[MAXN] ;
  43. vector<pair<ll,ll>> adj_normal[MAXN] ;
  44. //**Struct**//
  45. struct Edge {
  46.     ll u, v, w, id   ;
  47.     bool operator < (const Edge & other ) const {
  48.         return w < other. w ;
  49.     }
  50. } edge[MAXN];
  51. //**Function**//
  52. template<class X, class Y >
  53. bool minimize(X & x, const Y &y ) {
  54.     return x > y ? x = y, 1:0 ;
  55. }
  56. template<class X, class Y >
  57. bool maximize(X &x, const Y &y ) {
  58.     return x < y ? x = y, 1:0 ;
  59. }
  60. void dfs(ll u, ll p ) {
  61.  
  62. }
  63. void init() {
  64.     cin>>n >> m;
  65.     FOR(i,1, m  ) {
  66.         ll x, y, w ;
  67.         cin >> x >> y >> w;
  68.         adj_normal[x].push_back({y , w}) ;
  69.         adj_normal[y].push_back({x , w }) ;
  70.         edge[i] = {x,  y, w, i  } ;
  71.     }
  72. }
  73. void dfs_1(ll u, ll p ) {
  74.     for(auto [v, w ] : adj[u] ) if(v != p ) {
  75.             dfs_1(v, u ) ;
  76.             if(ma[v][1] + w > ma[u][1]) {
  77.                 ma[u][2] = ma[u][1] ;
  78.                 ma[u][1] = ma[v][1] + w ;
  79.             } else maximize(ma[u][2], ma[v][1] + w)  ;
  80.         }
  81. }
  82. void dfs_2(ll u, ll p ) {
  83.     for(auto [v, w] : adj[u]) if(v != p ) {
  84.             out[v] = out[u] + w ;
  85.             if(ma[v][1] + w == ma[u][1]) {
  86.                 maximize(out[v], ma[u][2] + w ) ;
  87.             } else maximize(out[v], ma[u][1] + w) ;
  88.             dfs_2(v, u ) ;
  89.         }
  90. }
  91. void check() {
  92.     memset(ma, 0, sizeof ma )  ;
  93.     memset(out, 0, sizeof out ) ;
  94.     dfs_1(1, 1) ;
  95.     dfs_2(1, 1 );
  96.     ll duongkinh = 0 ;
  97.     FOR(u, 1,  n ) maximize(duongkinh, ma[u][1] + out[u]) ;
  98.     if(minimize(min_res, duongkinh )) res = S_edge ;
  99. }
  100. void dijkstra(ll start ) {
  101.     FOR(i, 0, n  ) d[i] = INF ;
  102.     d[start] = 0 ;
  103.     priority_queue<pair<ll,ll>, vector<pair<ll,ll>>, greater<>> pq ;
  104.     pq.push({0, start } )  ;
  105.     while(!pq.empty() ) {
  106.         pair<ll,ll> u = pq.top() ;
  107.         pq.pop() ;
  108.         if(d[u.se] < u.fi ) continue ;
  109.         for(pair<ll,ll> v : adj_normal[u.se ] ) {
  110.             if(d[v.fi] > v.se + u.fi ) pq.push({d[v.fi] = v.se + u.fi, v.fi   }) ;
  111.         }
  112.     }
  113. }
  114. ll find_set(ll a) {
  115.     return lab[a] < 0 ? a : lab[a] = find_set(lab[a]) ;
  116. }
  117. bool union_set(ll a,ll b ) {
  118.     a = find_set(a) ;
  119.     b = find_set(b) ;
  120.     if(a == b) return false ;
  121.     if(lab[a] > lab[b] )swap(a, b ) ;
  122.     lab[a] += lab[b] ;
  123.     lab[b] = a;
  124.     return true ;
  125. }
  126. void build_tree() {
  127.  
  128.     FOR(i, 0, n ) lab[i] = -1, adj[i].clear() ;
  129.     S_edge.clear() ;
  130.     FOR(i, 1, m ) {
  131.         ll u = edge[i].u, v = edge[i].v, w = edge[i].w, id = edge[i].id ;
  132.         if(d[u] + w == d[v]|| d[v] + w == d[u]) {
  133.             if(union_set(u, v)) {
  134.                 adj[u].push_back({v, w}) ;
  135.                 adj[v].push_back({u, w}) ;
  136.                 S_edge.push_back(id) ;
  137.             }
  138.         }
  139.     }
  140. //    cout << S_edge.size() ; cout <<" run " << el ;
  141. }
  142. void solve() {
  143.  
  144.     FOR(i, 1,  n ) {
  145.         dijkstra(i) ;
  146.         build_tree() ;
  147.         check() ;
  148.     }
  149.  
  150.     cout << min_res << el ;
  151.     for(ll v : res ) cout << v << " " ;
  152. }
  153.  
  154. __ROOT__ {
  155.     // freopen(NAME".inp" , "r" , stdin);
  156.     // freopen(NAME".out" , "w", stdout) ;
  157.     fast;
  158.     int t = 1; // cin >> t ;
  159.     while(t--) {
  160.         init();
  161.         solve();
  162.     }
  163.     cerr << "Bố thí " << el  ; 
  164.     cout << "Bố thí " << el ; 
  165.     return (0&0);
  166. }
  167.  
  168.  
  169.  
  170.  
Success #stdin #stdout #stderr 0.01s 5328KB
comments (?)
stdin
copy 
Bố thí
stdout
copy 
1152921504606846976
Bố thí
stderr
copy 
Bố thí
https://ideone.com/mlCBuC
Bố thí
language:
C++14 (gcc 8.3)
created:
8 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!