fork download
copy 
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3.  
  4. #define FOR(i, a, b) for(int i = (a); i <= (b); ++i)
  5. #define FORD(i, a, b) for(int i = (a); i >= (b); --i)
  6. #define sz(a) (int)(a).size()
  7. #define all(a) (a).begin(), (a).end()
  8. #define bit(s, i) (((s) >> (i)) & 1)
  9. #define ii pair <int, int>
  10. #define fi first
  11. #define se second
  12. #define ll long long
  13. #define eb emplace_back
  14. #define pb push_back
  15. #define __builtin_popcount __builtin_popcountll
  16.  
  17. template <class X, class Y>
  18.     bool maxi(X &x, Y y) {
  19.         if(x < y) {
  20.             x = y;
  21.             return true;
  22.         }
  23.         return false;
  24.     }
  25.  
  26. template <class X, class Y>
  27.     bool mini(X &x, Y y) {
  28.         if(x > y) {
  29.             x = y;
  30.             return true;
  31.         }
  32.         return false;
  33.     }
  34.  
  35. void solve();
  36. int32_t main() {
  37.     #define task "test"
  38.     if(fopen(task".inp", "r")){
  39.         freopen(task".inp", "r", stdin);
  40.         freopen(task".out", "w", stdout);
  41.     }
  42.     cin.tie(0)->sync_with_stdio(0);
  43.  
  44.     int tc = 1; //cin >> tc;
  45.     FOR(i, 1, tc){
  46.         solve();
  47.     }
  48. }
  49.  
  50. const int N=3e5+5;
  51. const int LG=18;
  52. const int INF=2e9;
  53.  
  54. int n,m;
  55. pair<ii,int> ed[N];
  56.  
  57. int h[N],tin[N],tout[N],we[N],par[N],Time;
  58. bool isMST[N];
  59. vector<ii> adj[N];
  60.  
  61. void input(){
  62.     cin>>n>>m;
  63.     FOR(i,1,m){
  64.         int u,v,w; cin>>u>>v>>w;
  65.         ed[i]={{u,v},w};
  66.     }
  67.     sort(ed+1,ed+1+m,[](pair<ii,int>x,pair<ii,int>y){return x.se<y.se;});
  68. }
  69.  
  70. struct DSU{
  71.     int par[N];
  72.     int find(int a){
  73.         return par[a]==0?a:par[a]=find(par[a]);
  74.     }
  75.     bool unite(int a, int b){
  76.         a=find(a); b=find(b);
  77.         if(a!=b){
  78.             par[b]=a;
  79.             return true;
  80.         }
  81.         return false;
  82.     }
  83. } dsu1,dsu2;
  84.  
  85. void dfs(int u, int p){
  86.     tin[u]=++Time;
  87.     for(auto [v,w]:adj[u]) if(v!=p){
  88.         h[v]=h[u]+1;
  89.         par[v]=u;
  90.         we[v]=w;
  91.         dfs(v,u);
  92.     }
  93.     tout[u]=Time;
  94. }
  95.  
  96. bool isAncestor(int r, int u){
  97.     return tin[r]<=tin[u]&&tout[u]<=tout[r];
  98. }
  99.  
  100. void build_mst(){
  101.     FOR(i,1,m){
  102.         int u=ed[i].fi.fi, v=ed[i].fi.se, w=ed[i].se;
  103.         if(dsu1.unite(u,v)){
  104.             adj[u].eb(v,w);
  105.             adj[v].eb(u,w);
  106.             isMST[i]=true;
  107.         }
  108.     }
  109.     dfs(1,-1);
  110. }
  111.  
  112. int curw;
  113. bool isTurn[N];
  114.  
  115. struct segmentTree{
  116.     int st[N<<2],lz[N<<2];
  117.  
  118.     segmentTree(){
  119.         fill(begin(st),end(st),INF);
  120.         fill(begin(lz),end(lz),INF);
  121.     }
  122.  
  123.     void apply(int id, int val){
  124.         mini(st[id],val);
  125.         mini(lz[id],val);
  126.     }
  127.     void down(int id){
  128.         if(lz[id]==INF) return;
  129.         apply(id<<1,lz[id]);
  130.         apply(id<<1|1,lz[id]);
  131.         lz[id]=INF;
  132.     }
  133.     void upd(int u, int v, int val, int id, int l, int r){
  134.         if(u>r||v<l) return;
  135.         if(u<=l&&r<=v){
  136.             apply(id,val);
  137.             return;
  138.         }
  139.         int mid=(l+r)>>1;
  140.         down(id);
  141.         upd(u,v,val,id<<1,l,mid);
  142.         upd(u,v,val,id<<1|1,mid+1,r);
  143.         st[id]=min(st[id<<1],st[id<<1|1]);
  144.     }
  145.     void upd(int u, int v, int val){
  146.         upd(u,v,val,1,1,n);
  147.     }
  148.     void upd(int x, int val){
  149.         int id=1, l=1, r=n;
  150.         while(l<r){
  151.             int mid=(l+r)>>1;
  152.             down(id);
  153.             if(x<=mid){
  154.                 id=id<<1;
  155.                 r=mid;
  156.             }
  157.             else{
  158.                 id=id<<1|1;
  159.                 l=mid+1;
  160.             }
  161.         }
  162.         st[id]=val;
  163.         while(id>1){
  164.             id/=2;
  165.             st[id]=min(st[id<<1],st[id<<1|1]);
  166.         }
  167.     }
  168.     int get(int x){
  169.         int id=1, l=1, r=n;
  170.         while(l<r){
  171.             int mid=(l+r)>>1;
  172.             down(id);
  173.             if(x<=mid){
  174.                 id=id<<1;
  175.                 r=mid;
  176.             }
  177.             else{
  178.                 id=id<<1|1;
  179.                 l=mid+1;
  180.             }
  181.         }
  182.         return st[id];
  183.     }
  184.     int get(int u, int v, int id, int l, int r){
  185.         if(u>r||v<l) return INF;
  186.         if(u<=l&&r<=v) return st[id];
  187.         int mid=(l+r)>>1;
  188.         down(id);
  189.         return min(get(u,v,id<<1,l,mid),get(u,v,id<<1|1,mid+1,r));
  190.     }
  191.     int get(int u, int v){
  192.         return get(u,v,1,1,n);
  193.     }
  194. } seg_mi,seg_res;
  195.  
  196. void dfs_turn(int u){
  197.     isTurn[u]=true;
  198.     seg_res.upd(tin[u],seg_mi.get(tin[u])+curw);
  199.     for(auto [v,w]:adj[u]) if(v!=par[u]&&w<=curw){
  200.         dfs_turn(v);
  201.     }
  202. }
  203.  
  204. void main_solve(){
  205.     isTurn[1]=true;
  206.     FOR(i,2,n){
  207.         seg_mi.upd(tin[i],tout[i],we[i]);
  208.     }
  209.  
  210.     FOR(i,1,m){
  211.         int u=ed[i].fi.fi, v=ed[i].fi.se, w=ed[i].se; curw=w;
  212.         if(isMST[i]){
  213.             if(isTurn[u]&&isTurn[v]) continue;
  214.  
  215.             if(isTurn[u]) dfs_turn(v);
  216.             else if(isTurn[v]) dfs_turn(u);
  217.         }
  218.         else{
  219.             int rmi=1e9;
  220.             u=dsu2.find(u), v=dsu2.find(v);
  221.             while(!isAncestor(u,v)){
  222.                 mini(rmi,we[u]);
  223.                 dsu2.unite(par[u],u);
  224.                 u=dsu2.find(u);
  225.             }
  226.             while(!isAncestor(v,u)){
  227.                 mini(rmi,we[v]);
  228.                 dsu2.unite(par[v],v);
  229.                 v=dsu2.find(v);
  230.             }
  231.  
  232.             mini(we[u],rmi); mini(we[v],rmi);
  233.             seg_mi.upd(tin[u],tout[u],rmi);
  234.             seg_res.upd(tin[u],tout[u],rmi+curw);
  235.         }
  236.     }
  237.  
  238.     FOR(i,2,n) cout<<seg_res.get(tin[i])<<'\n';
  239. }
  240.  
  241. void solve() {
  242.     input();
  243.     build_mst();
  244.     main_solve();
  245. }
  246.  
Success #stdin #stdout 0.01s 35936KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
https://ideone.com/vGTUid
language:
C++ (gcc 8.3)
created:
11 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!