Statement
给出一个 $n$ 个点 $m$ 条边的无向图，每条边在 $l_i$ 时刻出现，$r_i$ 时刻消失。$0$ 时刻时你在 $1$ 号点上，每一时刻你都需要经过一条边移动到距离为 $1$ 的另一个点上，不能停留在一个点上不动。每个点和每条边均可经过多次。问最早到达 $n$ 号点的时间，或判断无法到达 $n$ 号点。
$n,m \le 5 \times 10^5,~0 \le l < r \le 10^9$
Solution
我们发现若我们在 $t$ 时刻从 $x$ 走到 $y$，我们可以在这一条边上反复横跳让我们在 $t + 2,~t + 4,~\dots$ 时刻均能到达 $y$，直到该边消失。由于这些能到达 $y$ 的时刻奇偶性均相同，因此考虑将每个点拆分为两个，一个为奇点一个为偶点，每次到达奇点时的时刻为奇数，到达偶点的时刻为偶数。对于一条 $x$ 向 $y$ 的边，拆点后即为 $x$ 的奇点向 $y$ 的偶点连边和 $x$ 的偶点向 $y$ 的奇点连边。
考虑在拆完点后得到的图上跑最短路，但是将最短路状态记在点上是不妥的，因为点是不会消失的，因此无法判断长于最短路的某一个路径长度是否合法。考虑将最短路状态记在边上，对每条有向边记录其最早的到达这条边起点的时间。到达一个点的最早时间即为他的所有入边的最短路的最小值加一。
Code
/**
* @file 827F.cpp
* @author Macesuted (i@macesuted.moe)
* @date 2022-04-03
*
* @copyright Copyright (c) 2022
* @brief
* My Tutorial: https://macesuted.moe/article/cf827f
*
*/
#include <bits/stdc++.h>
using namespace std;
namespace IO {
const int SIZE = 1 << 20;
char Ibuf[SIZE], *Il = Ibuf, *Ir = Ibuf, Obuf[SIZE], *Ol = Obuf, *Or = Ol + SIZE - 1;
int cache1[100], cache2[100];
char isspace(char c) { return c == ' ' || c == '\t' || c == '\n' || c == '\v' || c == '\f' || c == '\r'; }
char iseoln(char c) { return c == '\n' || c == '\r'; }
void fill(void) { return Ir = (Il = Ibuf) + fread(Ibuf, 1, SIZE, stdin), void(); }
void flush(void) { return fwrite(Obuf, 1, Ol - Obuf, stdout), Ol = Obuf, void(); }
char buftop(void) { return Ir == Il && (fill(), 1), *Il; }
char getch(void) { return Il == Ir ? fill(), Il == Ir ? EOF : *Il++ : *Il++; }
void putch(char x) { return *Ol++ = x, Ol == Or && (flush(), 1), void(); }
template <typename T = int>
T read(void) {
T x = 0, f = +1;
char c = getch();
while (c < '0' || c > '9') (c == '-') && (f = -f), c = getch();
while ('0' <= c && c <= '9') x = (x << 3) + (x << 1) + (c ^ 48), c = getch();
return x * f;
}
template <typename T>
void write(T x) {
if (!x) return putch('0');
if (x < 0) putch('-'), x = -x;
int top = 0;
while (x) cache1[top++] = x % 10, x /= 10;
while (top) putch(cache1[--top] ^ 48);
return;
}
template <typename T>
void writeDouble(T x, int dep = 10) {
if (x < 0) putch('-'), x = -x;
int64_t fx = x;
x -= fx;
for (int i = 0; i < dep; i++) cache2[i] = (x *= 10), x -= int(x);
if (int(x * 10) > 4) {
cache2[dep - 1]++;
for (int i = dep - 1; i; i--)
if (cache2[i] == 10) cache2[i] = 0, cache2[i - 1]++;
if (cache2[0] == 10) cache2[0] = 0, fx++;
}
write(fx), putch('.');
for (int i = 0; i < dep; i++) putch(cache2[i] ^ 48);
return;
}
string getstr(const string& suf = "") {
string s = suf;
while (isspace(buftop())) getch();
for (char* p = Il; Il != Ir; fill(), p = Il) {
while (Il < Ir && !isspace(*Il) && *Il != EOF) Il++;
s.append(p, Il);
if (Il < Ir) break;
}
return s;
}
string getline(const string& suf = "") {
string s = suf;
while (iseoln(buftop())) getch();
for (char* p = Il; Il != Ir; fill(), p = Il) {
while (Il < Ir && !iseoln(*Il) && *Il != EOF) Il++;
s.append(p, Il);
if (Il < Ir) break;
}
return s;
}
void putstr(string str, int begin = 0, int end = -1) {
if (end == -1) end = str.size();
for (int i = begin; i < end; i++) putch(str[i]);
return;
}
struct Flusher_ {
~Flusher_() { flush(); }
} io_flusher_;
} // namespace IO
using IO::getch;
using IO::getline;
using IO::getstr;
using IO::putch;
using IO::putstr;
using IO::read;
using IO::write;
using IO::writeDouble;
bool mem1;
#define maxn 500005
typedef tuple<int, int, int> tiii;
vector<vector<tiii>> graph;
vector<vector<tiii>::iterator> cur;
int dist[maxn];
void addEdge(int x, int y, int l, int r) {
return l <= r &&
(graph[x].emplace_back(l + (l & 1), r - (r & 1), y), graph[y].emplace_back(l + !(l & 1), r - !(r & 1), x), 1),
void();
}
void solve(void) {
int n = read(), m = read();
graph.resize(2 * n + 1), cur.resize(2 * n + 1);
for (int i = 1; i <= m; i++) {
int x = read(), y = read(), l = read(), r = read() - 1;
addEdge(x, y + n, l, r), addEdge(y, x + n, l, r);
}
for (int i = 1; i <= 2 * n; i++) sort(cur[i] = graph[i].begin(), graph[i].end());
memset(dist, 0x3f, sizeof(dist)), dist[1] = 0;
static priority_queue<tiii, vector<tiii>, greater<tiii>> que;
while (!que.empty()) que.pop();
while (cur[1] != graph[1].end() && get<0>(*cur[1]) == 0) que.emplace(1, get<1>(*cur[1]) + 1, get<2>(*cur[1])), cur[1]++;
while (!que.empty()) {
auto [l, r, x] = que.top();
que.pop(), dist[(x - 1) % n + 1] = min(dist[(x - 1) % n + 1], l);
for (auto& i = cur[x]; i != graph[x].end() && get<0>(*i) <= r; i++)
if (get<1>(*i) >= l) que.emplace(max(l, get<0>(*i)) + 1, get<1>(*i) + 1, get<2>(*i));
}
return write(dist[n] == 0x3f3f3f3f ? -1 : dist[n]), putch('\n');
}
bool mem2;
int main() {
ios::sync_with_stdio(false);
#ifdef MACESUTED
cerr << "Memory Cost: " << abs(&mem1 - &mem2) / 1024. / 1024. << "MB" << endl;
#endif
int _ = 1;
while (_--) solve();
#ifdef MACESUTED
cerr << "Time Cost: " << clock() * 1000. / CLOCKS_PER_SEC << "MS" << endl;
#endif
return 0;
}
Comments | NOTHING