BOJ 28399 - 황혼

BOJ 28399 - 황혼

모든 정점이 최대 하나의 경로에만 포함되므로 현재 $i$ 번 정점이라고 할 때 이 정점이 속한 경로의 시작점부터 출발해서 여기까지 온건지, 아니면 상관없는지를 저장할 수 있다.

따라서 $2N$ 개의 정점에 대해 다익스트라를 때려주면 된다.

경로에서 첫 번째 정점에 진입할 때와 현재 경로에 있는 어떤 정점인데 이 경로에서 그 다음 정점으로 갈 때만 현재 해당 정점에 있는 경로에 포함이 되어있다는 플래그를 설정해줄 수 있다.

const int inf = 2e18;
void solve() {
   int n, m, k;
   cin >> n >> m >> k;
   vector<vector<pi>> edges(n);
   for (int i = 0; i < m; i++) {
      int u, v, w;
      cin >> u >> v >> w, u--, v--;
      edges[u].pb({v, w});
   }
   vi group(n, -1), nxt(n, -1);
   vvi paths(k);
   vvi dist(n, vi(2, inf));
   for (int i = 0; i < k; i++) {
      int s;
      cin >> s;
      for (int j = 0; j < s; j++) {
         int t;
         cin >> t;
         t--;
         if (sz(paths[i])) nxt[paths[i].back()] = t;
         paths[i].pb(t);
         group[t] = i;
      }
   }
   priority_queue<array<int, 3>, vector<array<int, 3>>, greater<>> pq;

   if (group[0] == -1 || paths[group[0]][0] != 0) {
      dist[0][0] = 0;
      pq.push({0, 0, 0});
   } else {
      dist[0][1] = 0;
      pq.push({0, 0, 1});
   }

   while (sz(pq)) {
      auto [cur_d, cur, is_in] = pq.top();
      pq.pop();
      if (dist[cur][is_in] != cur_d) continue;

      for (auto &[to, w]: edges[cur]) {
         if (is_in && nxt[cur] == to) {

            if (nxt[to] == -1) continue;

            if (dist[to][1] > cur_d + w) {
               dist[to][1] = cur_d + w;
               pq.push({dist[to][1], to, 1});
            }
         } else {
            if (group[to] != -1 && paths[group[to]][0] == to) {
               if (dist[to][1] > cur_d + w) {
                  dist[to][1] = cur_d + w;
                  pq.push({dist[to][1], to, 1});
               }
            } else {
               if (dist[to][0] > cur_d + w) {
                  dist[to][0] = cur_d + w;
                  pq.push({dist[to][0], to, 0});
               }
            }
         }
      }
   }

   for (int i = 0; i < n; i++) {
      int mn = min(dist[i][0], dist[i][1]);
      if (mn == inf) cout << -1 << ' ';
      else cout << mn << ' ';
   }
}