CF1725M Moving Both Hands 做题笔记

发布于

题意

给出一个 $n$ 个点 $m$ 条边的有向图,点的编号为 $1$ 到 $n$,第 $i$ 条边从 $u_i$ 出发连向 $v_i$,长度为 $w_i$。

你想要在这张图上玩若干轮游戏。在一轮游戏中,你会先选定一个点 $p \neq 1$,接着在 $1$ 号点和 $p$ 分别放置一枚金币。你可以沿着有向边任意移动金币,但需要花费边长对应的时间。你的目标是要让两枚金币移动到同一个点,并且最小化总时间。

对于每个 $2 \leq i \leq n$,你都要输出如果选定 $p = i$ 时最小的时间花费。如果两枚金币不可能移到同一个点,则输出 $−1$。

题解

比较妙的建模。
可以建一层正向图,再建一个反向图。从正向图中的一个点可以直接跃迁到反向图。而反向图不能回到正向图。

代码

dijkstra 版:

// Please submit with C++17! It's best to use C++20 or higher version.
// By Koicy (https://koicy.ly)
// rbtree (i@koicy.ly)
// This is my kingdom come.

// #define EFILE ""
#include <algorithm>
#include <array>
#include <cmath>
#include <cstring>
#include <iomanip>
#include <iostream>
#include <list>
#include <map>
#include <numeric>
#include <queue>
#include <random>
#include <set>
#include <stack>
#include <string>
#include <tuple>
#include <unordered_map>
#include <utility>
#include <vector>
#define _CONSOLE 0

using namespace std;
using tp = long long;
constexpr tp ZERO = 0, ONE = 1, INF32 = 1073741823, INF = 0x3fffffffffffffff;

// :/

void MIST() {
}

constexpr tp Hat_N = 2e5 + 3;

bool vis[Hat_N];
tp dist[Hat_N];
vector<pair<tp, tp>> e[Hat_N];

void dijkstra(tp s) {
  priority_queue<pair<tp, tp>, vector<pair<tp, tp>>, greater<pair<tp, tp>>> q;
  memset(dist, 0x3f, sizeof dist);
  memset(vis, 0, sizeof vis);
  dist[s] = 0;
  for (q.emplace(0, s); q.size();) {
    tp l = q.top().second;
    q.pop();
    if (!vis[l]) {
      vis[l] = true;
      for (auto& t : e[l]) {
        tp i = t.first, j = t.second;
        if (dist[i] > dist[l] + j) {
          dist[i] = dist[l] + j;
          if (!vis[i]) q.emplace(dist[i], i);
        }
      }
    }
  }
}

void STRUGGLING([[maybe_unused]] tp TEST_NUMBER) {
  tp n, m;
  cin >> n >> m;
  while (m--) {
    tp u, v, w;
    cin >> u >> v >> w;
    e[u].emplace_back(v, w);
    e[v + n].emplace_back(u + n, w);
  }
  for (tp i = 1; i <= n; ++i) e[i].emplace_back(i + n, 0);
  dijkstra(1);
  for (tp i = 2; i <= n; ++i)
    cout << (dist[i + n] * 2 > INF ? -1 : dist[i + n]) << " \n"[i == n];
}

#include <fstream>
  
signed main() {
  tp t = 0, _t = 1;
  cin.tie(0)->sync_with_stdio(0);
#if !_CONSOLE
#ifdef _LOCAL
  static ifstream _in("input.txt");
  cin.rdbuf(_in.rdbuf());
#else
#ifdef EFILE
  static ifstream _in(EFILE ".in");
  static ofstream _out(EFILE ".out");
  cin.rdbuf(_in.rdbuf());
  cout.rdbuf(_out.rdbuf());
#endif
#endif
#endif
  // cin >> _t;
  MIST();
  while (t < _t) STRUGGLING(++t);
  return 0;
}

//*/

暂无评论

发表评论