[ABC257F] Teleporter Setting Solution

更好的阅读体验戳此进入

题面

存在 $n$$n$ 个小镇，$m$$m$ 条传送通道，第 $i$$i$ 条双向连结 $u_i,v_i$$u_i, v_i$ 两个小镇，经过每个传送通道需要花费 $1$$1$ 分钟。特别地，可能存在 $u_i=0$$u_i = 0$，表示该条传送通道只规定了一端，另一端待定。存在 $n$$n$ 个独立询问，对于 $i=1,2,\cdots ,n$$i = 1, 2, \cdots, n$，钦定所有未确定的 $u_i$$u_i$ 均为 $i$$i$，求从小镇 $1$$1$ 到小镇 $n$$n$ 最小耗费的时间。若无法到达输出 $-1$$-1$。

Solution

算是一道挺好的题。首先我们可以进行如下转化，对于所有 $u_i=0$$u_i = 0$ 的边，我们将其连结到一个超级源点 $S$$S$ 上，不失一般性，设 $S=0$$S = 0$，此时对于每次询问，我们仅需要对 $S\to i$$S \rightarrow i$ 连边即可。当然我们肯定不能每次都算一遍，于是考虑发现，对于 $1\to n$$1 \rightarrow n$ 的路径，一共仅可能存在如下几种贡献：$1\to n$$1 \rightarrow n$，$1\to S\to i\to n$$1 \rightarrow S \rightarrow i \rightarrow n$，$1\to i\to S\to n$$1 \rightarrow i \rightarrow S \rightarrow n$，同时注意我们这里的箭头不是表示直接到达，而是表示最短路。所以以此不难发现，我们所需要维护的就只有 $1$$1$ 和 $n$$n$ 为源点的单源最短路，即可表示出来每次的值。然后每次在这些里取 $min$$\min$ 即可，记得判一下无解。

Code

xxxxxxxxxx
88
1
#define _USE_MATH_DEFINES
2
#include <bits/stdc++.h>
3

4
#define PI M_PI
5
#define E M_E
6
#define npt nullptr
7
#define SON i->to
8
#define OPNEW void* operator new(size_t)
9
#define ROPNEW(arr) void* Edge::operator new(size_t){static Edge* P = arr; return P++;}
10

11
using namespace std;
12

13
mt19937 rnd(random_device{}());
14
int rndd(int l, int r){return rnd() % (r - l + 1) + l;}
15
bool rnddd(int x){return rndd(1, 100) <= x;}
16

17
typedef unsigned int uint;
18
typedef unsigned long long unll;
19
typedef long long ll;
20
typedef long double ld;
21

22
template < typename T = int >
23
inline T read(void);
24

25
struct Edge{
26
    Edge* nxt;
27
    int to;
28
    OPNEW;
29
}ed[610000];
30
ROPNEW(ed);
31
Edge* head[310000];
32

33
int N, M;
34
int dis1[310000], disn[310000];
35

36
void bfs1(void){
37
    memset(dis1, 0x3f, sizeof dis1);
38
    bitset < 310000 > vis; vis.reset();
39
    queue < int > cur; cur.push(1), vis[1] = true, dis1[1] = 0;
40
    while(!cur.empty()){
41
        int p = cur.front(); cur.pop();
42
        for(auto i = head[p]; i; i = i->nxt)
43
            if(!vis[SON])
44
                vis[SON] = true, dis1[SON] = dis1[p] + 1, cur.push(SON);
45
    }
46
}
47
void bfsn(void){
48
    memset(disn, 0x3f, sizeof disn);
49
    bitset < 310000 > vis; vis.reset();
50
    queue < int > cur; cur.push(N), vis[N] = true, disn[N] = 0;
51
    while(!cur.empty()){
52
        int p = cur.front(); cur.pop();
53
        for(auto i = head[p]; i; i = i->nxt)
54
            if(!vis[SON])
55
                vis[SON] = true, disn[SON] = disn[p] + 1, cur.push(SON);
56
    }
57
}
58

59
int main(){
60
    N = read(), M = read();
61
    for(int i = 1; i <= M; ++i){
62
        int s = read(), t = read();
63
        head[s] = new Edge{head[s], t};
64
        head[t] = new Edge{head[t], s};
65
    }bfs1(), bfsn();
66
    for(int i = 1; i <= N; ++i){
67
        int ans = min({dis1[N], dis1[0] + disn[i], dis1[i] + disn[0]});
68
        printf("%d%c", ans >= 0x3f3f3f3f ? -1 : ans, i == N ? '\n' : ' ');
69
    }
70
    fprintf(stderr, "Time: %.6lf\n", (double)clock() / CLOCKS_PER_SEC);
71
    return 0;
72
}
73

74
template < typename T >
75
inline T read(void){
76
    T ret(0);
77
    int flag(1);
78
    char c = getchar();
79
    while(c != '-' && !isdigit(c))c = getchar();
80
    if(c == '-')flag = -1, c = getchar();
81
    while(isdigit(c)){
82
        ret *= 10;
83
        ret += int(c - '0');
84
        c = getchar();
85
    }
86
    ret *= flag;
87
    return ret;
88
}

UPD

update-2022_12_09 初稿