存在
算是一道挺好的题。首先我们可以进行如下转化,对于所有
xxxxxxxxxx
881
2
3
4
5
6
7
8
9
10
11using namespace std;
12
13mt19937 rnd(random_device{}());
14int rndd(int l, int r){return rnd() % (r - l + 1) + l;}
15bool rnddd(int x){return rndd(1, 100) <= x;}
16
17typedef unsigned int uint;
18typedef unsigned long long unll;
19typedef long long ll;
20typedef long double ld;
21
22template < typename T = int >
23inline T read(void);
24
25struct Edge{
26 Edge* nxt;
27 int to;
28 OPNEW;
29}ed[610000];
30ROPNEW(ed);
31Edge* head[310000];
32
33int N, M;
34int dis1[310000], disn[310000];
35
36void 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}
47void 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
59int 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
74template < typename T >
75inline 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}
update-2022_12_09 初稿