BOJ 27848 - Moo Route II

BOJ 27848 - Moo Route II

일반적으로 최단 경로 알고리즘을 쓰면 TLE가 나오는 데이터가 껴있다.

우리가 어떤 정점 $u$에 있고 $u+a_u$ 이상의 $r$(출발 시간) 을 가진 간선들만 본다고 하자.

어떤 간선이 $u \to v$ 일 때, 그 간선을 두 번 볼일이 있을까?

1. 그 간선으로 $v$의 최단 경로가 $s$로 업데이트 되었다면 그 간선은 더 이상 쓰일 필요가 없다.
2. 그 간선으로 $v$의 최단 경로가 업데이트 되지 않았다면 $v$ 는 이미 $s$ 보다 빠른 최단 경로를 가지고 있으므로 더 이상 쓰일 필요가 없다.

따라서 모든 간선은 최대 한 번만 쓰이므로 한 번 본 간선은 지워주는 식으로 $O(M)$ 으로 문제를 해결할 수 있다.

엄밀히 말하면 간선들을 빨리 지워주기 위해 정렬 과정이 있으므로 $O(M\log M)$ 이다.

모든 간선을 한 번만 보기 때문이다.

void solve() {  
   int n, m;  
   cin >> n >> m;  
  
   vector<vector<array<int, 3>>> edges(n);  
   vi a(n);  
   for (int i = 0; i < m; i++) {  
      // c 공항에서 r 시간에 타서 d 공항의 s 시간에 도착, 과거로 갈 수도 있다.  
      int c, r, d, s;  
      cin >> c >> r >> d >> s;  
      c--, d--;  
      edges[c].pb({r, d, s});  
   }  
   for (int i = 0; i < n; i++) {  
      sort(all(edges[i]), [&](auto &a, auto &b) {  
         return a[0] < b[0];  
      });  
   }  
   fv(a);  
   const int inf = 2e15;  
  
   vi dist(n, inf);  
   dist[0] = 0;  
   queue<pi> q;  
   q.push({0, 1});  
   while (sz(q)) {  
      auto[cur, is_first_flight] = q.front();  
      q.pop();  
  
      int at_least = dist[cur] + (is_first_flight ? 0 : a[cur]);  
      for (int i = sz(edges[cur]) - 1; i >= 0 && edges[cur][i][0] >= at_least; i--) {  
         auto[r, d, s] = edges[cur][i];  
         if (dist[d] > s) {  
            dist[d] = s;  
            q.push({d, 0});  
         }  
         edges[cur].pop_back();  
      }  
      while (sz(edges[cur]) && edges[cur].back()[0] >= at_least)  
         edges[cur].pop_back();  
   }  
   for (int i = 0; i < n; i++) {  
      if (dist[i] == inf) cout << -1 << endl;  
      else cout << dist[i] << endl;  
   }  
}