Submission #1603231

---

Source Code Expand

#include<bits/stdc++.h>
using namespace std;

typedef pair<uint32_t,uint32_t> P;
int BitSearchReverse(uint32_t x){
  if(x==0)return -1;
  return 31-__builtin_clz(x);
}
struct RadixHeap{
  vector<P>v[33];
  uint32_t last,sz;
  RadixHeap(){
    last=sz=0;
  }
  void push(uint32_t x,uint32_t y){
    assert(last<=x);
    sz++;
    v[BitSearchReverse(x^last)+1].push_back({x,y});
  }
  void push(P p){
    push(p.first,p.second);
  }
  P top(){
    return pop(false);
  }
  P pop(bool f=true){
    assert(sz);
    if(!v[0].size()){
      int i=1;
      while(!v[i].size())++i;
      last=min_element(v[i].begin(),v[i].end())->first;
      for(P p:v[i])v[BitSearchReverse(p.first^last)+1].push_back(p);
      v[i].clear();
    }
    P r=v[0].back();
    if(f){
      sz--;
      v[0].pop_back();
    }
    return r;
  }
  int size(){
    return sz;
  }
  bool empty(){
    return sz==0;
  }
  void clear(){
    last=sz=0;
    for(auto a:v)a.clear();
  }
};
struct Graph{
  Graph(int n):E(n),d(n){}
  vector<vector<P>>E;
  vector<int>d;
  void add_edge(int a,int b,int c){
    E[a].push_back({b,c});
  }
  void dijkstra(int s){
    RadixHeap H;
    fill(d.begin(),d.end(),1e9);
    H.push({d[s]=0,s});
    while(H.size()){
      P p=H.top();H.pop();
      if(p.first>d[p.second])continue;
      for(P& a:E[p.second]){
        int x=a.first,y=a.second+p.first;
        if(y<d[x])d[x]=y,H.push({y,x});
      }
    }
  }
};

main(){
  int n,m,a,b,c,x=1e9;
  cin>>n>>m;
  Graph E(n);
  for(int i=0;i<m;++i){
    cin>>a>>b>>c;
    E.add_edge(--a,--b,c),E.add_edge(b,a,c);
  }
  for(int i=0;i<n;++i){
    E.dijkstra(i);
    x=min(x,*max_element(E.d.begin(),E.d.end()));
  }
  cout<<x<<endl;
}

Submission Info

Judge Result