Submission #616694

---

Source Code Expand

#ifndef KOMAKI_LOCAL
#define NDEBUG
#endif

#include <bits/stdc++.h>
#include <sys/time.h>
#include <unistd.h>
using namespace std;
#define i64         int64_t
#define rep(i, n)   for(i64 i = 0; i < ((i64)(n)); ++i)
#define sz(v)       ((i64)((v).size()))
#define bit(n)      (((i64)1)<<((i64)(n)))
#define all(v)      (v).begin(), (v).end()

std::string dbgDelim(int &i){ return (i++ == 0 ? "" : ", "); }
#define dbgEmbrace(exp) { int i = 0; os << "{"; { exp; } os << "}"; return os; }
template <class T> std::ostream& operator<<(std::ostream &os, std::vector<T> v);
template <class T> std::ostream& operator<<(std::ostream &os, std::set<T> v);
template <class T> std::ostream& operator<<(std::ostream &os, std::queue<T> q);
template <class T> std::ostream& operator<<(std::ostream &os, std::priority_queue<T> q);
template <class T, class K> std::ostream& operator<<(std::ostream &os, std::pair<T, K> p);
template <class T, class K> std::ostream& operator<<(std::ostream &os, std::map<T, K> mp);
template <class T, class K> std::ostream& operator<<(std::ostream &os, std::unordered_map<T, K> mp);
template <int INDEX, class TUPLE> void dbgDeploy(std::ostream &os, TUPLE tuple){}
template <int INDEX, class TUPLE, class H, class ...Ts> void dbgDeploy(std::ostream &os, TUPLE t)
{ os << (INDEX == 0 ? "" : ", ") << get<INDEX>(t); dbgDeploy<INDEX + 1, TUPLE, Ts...>(os, t); }
template <class T, class K> void dbgDeploy(std::ostream &os, std::pair<T, K> p, std::string delim)
{ os << "(" << p.first << delim << p.second << ")"; }
template <class ...Ts> std::ostream& operator<<(std::ostream &os, std::tuple<Ts...> t)
{ os << "("; dbgDeploy<0, std::tuple<Ts...>, Ts...>(os, t); os << ")"; return os; }
template <class T, class K> std::ostream& operator<<(std::ostream &os, std::pair<T, K> p)
{ dbgDeploy(os, p, ", "); return os; }
template <class T> std::ostream& operator<<(std::ostream &os, std::vector<T> v)
{ dbgEmbrace( for(T t: v){ os << dbgDelim(i) << t; }); }
template <class T> std::ostream& operator<<(std::ostream &os, std::set<T> s)
{ dbgEmbrace( for(T t: s){ os << dbgDelim(i) << t; }); }
template <class T> std::ostream& operator<<(std::ostream &os, std::queue<T> q)
{ dbgEmbrace( for(; q.size(); q.pop()){ os << dbgDelim(i) << q.front(); }); }
template <class T> std::ostream& operator<<(std::ostream &os, std::priority_queue<T> q)
{ dbgEmbrace( for(; q.size(); q.pop()){ os << dbgDelim(i) << q.top();   }); }
template <class T, class K> std::ostream& operator<<(std::ostream &os, std::map<T, K> mp)
{ dbgEmbrace( for(auto p: mp){ os << dbgDelim(i); dbgDeploy(os, p, "->"); }); }
template <class T, class K> std::ostream& operator<<(std::ostream &os, std::unordered_map<T, K> mp)
{ dbgEmbrace( for(auto p: mp){ os << dbgDelim(i); dbgDeploy(os, p, "->"); }); }
#define DBG_OUT std::cerr
#define DBG_OVERLOAD(_1, _2, _3, _4, _5, _6, macro_name, ...) macro_name
#define DBG_LINE() { char s[99]; sprintf(s, "line:%3d | ", __LINE__); DBG_OUT << s; }
#define DBG_OUTPUT(v) { DBG_OUT << (#v) << "=" << (v); }
#define DBG1(v, ...) { DBG_OUTPUT(v); }
#define DBG2(v, ...) { DBG_OUTPUT(v); DBG_OUT << ", "; DBG1(__VA_ARGS__); }
#define DBG3(v, ...) { DBG_OUTPUT(v); DBG_OUT << ", "; DBG2(__VA_ARGS__); }
#define DBG4(v, ...) { DBG_OUTPUT(v); DBG_OUT << ", "; DBG3(__VA_ARGS__); }
#define DBG5(v, ...) { DBG_OUTPUT(v); DBG_OUT << ", "; DBG4(__VA_ARGS__); }
#define DBG6(v, ...) { DBG_OUTPUT(v); DBG_OUT << ", "; DBG5(__VA_ARGS__); }

#define DEBUG0() { DBG_LINE(); DBG_OUT << std::endl; }
#define DEBUG(...)                                                      \
  {                                                                     \
    DBG_LINE();                                                         \
    DBG_OVERLOAD(__VA_ARGS__, DBG6, DBG5, DBG4, DBG3, DBG2, DBG1)(__VA_ARGS__); \
    DBG_OUT << std::endl;                                               \
  }



#include <bits/stdc++.h>

template <typename T> class Dijkstra
{
public:
  Dijkstra<T>& addEdge(int from, int dest, T cost);
  void update(int source);
  T getDistance(int vertex);

  ~Dijkstra();
  Dijkstra(int vertex_num);

private:
  const int vertex_num;
  T *distances;

  class Edge
  {
  public:
    int target;
    T distance;
    Edge(int target, T distance) : target(target), distance(distance) {}
  };
  std::vector<Edge> *edges;

  class QueueElement
  {
  public:
    T distance;
    int vertex;
    inline QueueElement(T distance, int vertex) : distance(distance), vertex(vertex){}
    inline bool operator>(const QueueElement &e)const{ return distance > e.distance; }
  };
};

template <typename T>
inline Dijkstra<T>::~Dijkstra()
{
  delete [] edges;
  delete [] distances;
}

template <typename T>
inline Dijkstra<T>::Dijkstra(int vertex_num) : vertex_num(vertex_num)
{
  edges = new std::vector<Edge>[vertex_num];
  distances = new T[vertex_num];
}

template <typename T>
inline T Dijkstra<T>::getDistance(int vertex)
{
  return distances[vertex];
}

template <typename T>
inline void Dijkstra<T>::update(int source)
{
  memset(distances, -1, sizeof(T) * vertex_num);

  std::priority_queue<QueueElement, std::vector<QueueElement>, std::greater<QueueElement> > q;
  distances[source] = 0;
  q.push(QueueElement(0, source));

  for(int total_size = 1; 0 < total_size;){
    int vertex = q.top().vertex;
    T distance = q.top().distance;
    q.pop();
    if(distances[vertex] < distance) continue;
    --total_size;

    for(Edge e : edges[vertex]){
      int next_vertex = e.target;
      T next_distance = e.distance + distance;
      if(distances[next_vertex] == -1){
        ++total_size;
        distances[next_vertex] = next_distance;
        q.push(QueueElement(next_distance, next_vertex));
      }else if(next_distance < distances[next_vertex]){
        distances[next_vertex] = next_distance;
        q.push(QueueElement(next_distance, next_vertex));
      }
    }
  }
}

template <typename T>
inline Dijkstra<T>& Dijkstra<T>::addEdge(int from, int dest, T cost)
{
  edges[from].push_back(Edge(dest, cost));
  return *this;
}





int main()
{
  i64 n, m, s, t;
  cin >> n >> m >> s >> t;

  Dijkstra<i64> dijkstra(n);
  vector<vector<pair<pair<i64, i64>, pair<i64, i64>>>> edges(n);

  rep(i, m){
    i64 l;
    cin >> l;
    vector<i64> stations(l);
    vector<i64> distances(l - 1);
    vector<i64> distances_to_first(l);
    vector<i64> distances_to_last(l);
    rep(j, l) cin >> stations[j];
    rep(j, l - 1) cin >> distances[j];
    distances_to_first[0] = 0;
    rep(j, l - 1) distances_to_first[j + 1] = distances_to_first[j] + distances[j];
    distances_to_last[0] = distances_to_first[l - 1];
    rep(j, l - 1) distances_to_last[j + 1] = distances_to_last[j] - distances[j];
    assert(distances_to_last[l - 1] == 0);

    rep(j, l - 1){
      edges[stations[j + 0]].push_back(make_pair(make_pair(stations[j + 1], distances[j]), make_pair(stations[l - 1], distances_to_last [j + 0])));
      edges[stations[j + 1]].push_back(make_pair(make_pair(stations[j + 0], distances[j]), make_pair(stations[0]    , distances_to_first[j + 1])));
    }

    rep(j, l - 1){
      dijkstra.addEdge(stations[j + 0], stations[j + 1], distances[j]);
      dijkstra.addEdge(stations[j + 1], stations[j + 0], distances[j]);
    }
  }

  dijkstra.update(t);
  //rep(i, n) DEBUG(i, dijkstra.getDistance(i));

  i64 low = 0, high = bit(30);
  while(low + 1 < high){
    i64 limit = (low + high) / 2;

    bool ok = false;
    typedef pair<i64, i64> e;
    priority_queue<e, vector<e>, greater<e>> q;
    q.push(make_pair((i64)0, s));
    vector<i64> bests(n, bit(50));
    bests[s] = 0;

    while(sz(q)){
      i64 dist = q.top().first;
      i64 pos = q.top().second;
      q.pop();
      if(pos == t){
        ok = true;
        break;
      }
      if(bests[pos] < dist) continue;

      for(auto &p: edges[pos]){
        if(limit < dist + p.second.second + dijkstra.getDistance(p.second.first)) continue;
        i64 next_pos = p.first.first;
        i64 next_dist = dist + p.first.second;
        if(bests[next_pos] <= next_dist) continue;
        bests[next_pos] = next_dist;
        q.push(make_pair(next_dist, next_pos));
      }
    }

    if(ok) high = limit;
    else low = limit;
  }

  cout << high << endl;
}

Submission Info

Judge Result