CodeTON Round 5 (Div. 1 + Div. 2, Rated, Prizes!) - D. Tenzing and His Animal Friends

D. Tenzing and His Animal Friends

지문이 진짜 미친놈인데, $m$개의 조건이 도대체 뭘 의미하는건지 한참 생각했다.

노는 시간 중 $u, v$가 정확히 한 명만 있는 노는 시간이 $y$ 이하여야 한다는 조건이다.

이 조건을 이용해 이걸 최단거리 문제로 환원할 수 있다.

$1\ 3 \ 5$ 라는 조건이 있다고 하자.

그럼 $1$은 항상 껴있으므로 $1???\dots$으로 시작을 하고 $3$ 은 5초 뒤에 들어갈 수 있다는 것이다.

대략 정답은 다음과 같이 구성될 수 있겠다.

1?0??... 5
1?1??... ?

그래서 일단 $1$에서 시작하는 최단거리를 모두 구해서 $n$ 까지 최단거리를 구하자.

$n$까지 도달할 수 없다면 $1 \sim n-1$ 을 모두 $1$ 로 처리해버린다음에 무한히 진행할 수 있어서 정답은 inf 이다.

그렇지 않다면 정답은 $T=d_n$ 이다.

정답을 구성하는 방법은 최단거리를 기준으로 오름차순 정렬하고 현재 보고있는 인덱스는 뒤에 모두 계속 $1$로 바꿔주는 것이다.

같은 dist를 가진것들은 한 번에 처리해주면 된다.

바로 이전 값과의 $d$ 차이를 기록하고, 이전 값의 $t$ 값을 이 차이로 넣어준다.

그다음 마지막에는 정답 하나를 지운다. $n$이 $1$이 들어가는 행이 하나 생기기 때문이다.

const int inf = 2e18;  
  
void solve() {  
   int n, m;  
   cin >> n >> m;  
   vi dist(n, inf);  
   vector<vector<pi>> edges(n);  
   for (int i = 0; i < m; i++) {  
      int u, v, y;  
      cin >> u >> v >> y, u--, v--;  
      edges[u].pb({v, y});  
      edges[v].pb({u, y});  
   }  
   dist[0] = 0;  
   queue<int> q;  
   q.push(0);  
   while (sz(q)) {  
      int cur = q.front();  
      q.pop();  
      for (auto &[to, w]: edges[cur]) {  
         if (dist[to] > w + dist[cur]) {  
            dist[to] = w + dist[cur];  
            q.push(to);  
         }  
      }  
   }  
   if (dist[n - 1] == inf) {  
      cout << "inf";  
      return;  
   }  
  
   vector<pair<string, int>> ans;  
   vi idx(n);  
   iota(all(idx), 0);  
   for (int i = 0; i < n; i++) mina(dist[i], dist[n - 1]);  
   sort(all(idx), [&](int i, int j) { return dist[i] != dist[j] ? dist[i] < dist[j] : i < j; });  
   vi in(n);  
   debug(dist[n - 1]);  
   cout << dist[n - 1] << ' ';  
   for (int _i = 0, last = 0; _i < n;) {  
      int i = idx[_i];  
      int _j = _i;  
      while (_j < n && dist[idx[_j]] == dist[i]) {  
         in[idx[_j]] = 1;  
         _j++;  
      }  
  
      int dt = dist[i] - last;  
  
      if (_i) ans.back().se = dt;  
      ans.pb({string(n, '0'), 0});  
  
      for (int k = 0; k < n; k++) if (in[k]) ans.back().fi[k] = '1';  
  
      last = dist[i];  
      _i = _j;  
   }  
   ans.pop_back();  
   cout << sz(ans) << endl;  
   for (auto &[a, b]: ans) cout << a << ' ' << b << endl;  
}