杭电多校Age_of_Moyu

Age of Moyu

题解

标程的set+bfs貌似有漏洞。

1
2
3
4
5
6
7
5 6
1 2 1
2 3 1
3 4 1
4 5 1
1 3 2
1 4 3

这个数据就可以hack掉了。

所以我果断copy了dls队伍的代码。(用边做)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
#include <stdio.h>
#include <string.h>
#include <stdlib.h>
#include <iostream>
#include <algorithm>
#include <queue>
using namespace std;
inline char inputchar()
{
return getchar();
}
inline void inputnum(int &ret)
{
char ch = inputchar();
while(ch < '0' || ch > '9')
ch = inputchar();
ret = ch - '0';
ch = inputchar();
while(ch >= '0' && ch <= '9')
{
ret = ret * 10 + ch - '0';
ch = inputchar();
}
}
const int MAXN = 101010, MAXM = 202020;
int n, m;
class Edge
{
public:
int to, c, next;
}e[MAXM * 2];
int en, head[MAXN];
int dis[MAXM];
deque<int> q;
void insert()
{
int u, v, c;
// scanf("%d%d%d", &u, &v, &c);
inputnum(u);
inputnum(v);
inputnum(c);
e[++en].to = v;
e[en].c = c;
e[en].next = head[u];
head[u] = en;
e[++en].to = u;
e[en].c = c;
e[en].next = head[v];
head[v] = en;
}
bool solve()
{
if(scanf("%d%d", &n, &m) != 2)
return false;
memset(head, -1, (n + 2) * sizeof(int));
en = 1;
for(int i = 1; i <= m; i++)
insert();
memset(dis, 1, (m + 2) * sizeof(int));
for(int i = head[1]; i > 0; i = e[i].next)
dis[i / 2] = 1, q.push_back(i / 2);
while(!q.empty())
{
int now = q.front();
q.pop_front();
for(int i = head[e[now * 2].to]; i > 0; i = e[i].next)
if(e[i].c == e[now * 2].c)
{
if(dis[i / 2] > dis[now])
dis[i / 2] = dis[now], q.push_front(i / 2);
}
else
{
if(dis[i / 2] > dis[now] + 1)
dis[i / 2] = dis[now] + 1, q.push_back(i / 2);
}
for(int i = head[e[now * 2 + 1].to]; i > 0; i = e[i].next)
if(e[i].c == e[now * 2 + 1].c)
{
if(dis[i / 2] > dis[now])
dis[i / 2] = dis[now], q.push_front(i / 2);
}
else
{
if(dis[i / 2] > dis[now] + 1)
dis[i / 2] = dis[now] + 1, q.push_back(i / 2);
}
}
int ans = MAXM;
for(int i = head[n]; i > 0; i = e[i].next)
if(ans > dis[i / 2])
ans = dis[i / 2];
if(ans == MAXM)
ans = -1;
printf("%d\n", ans);
return true;
}
int main()
{
#ifdef LOCAL
freopen("a.in","r",stdin);
#endif
while(solve());
return 0;
}

时间卡的非常紧。优化了很多终于2.4s过了。

$$O(n^2)$$

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
#include<bits/stdc++.h>
using namespace std;
#define rep(i,a,n) for(int i=(a);i<(n);i++)
#define per(i,a,n) for(int i=(n-1);i>=(a);i--)
#define fi first
#define se second
typedef pair <int,int> pII;
typedef long long ll;
const int INF = 0x3f3f3f3f;
//head
void read(int &x){
char ch = getchar();x = 0;
for (; ch < '0' || ch > '9'; ch = getchar());
for (; ch >='0' && ch <= '9'; ch = getchar()) x = x * 10 + ch - '0';
}
const int maxn = 1e5 + 10;
int n,m,ans,cnt;
int head[maxn],dis[maxn<<1];
struct Edge{
int to,next,idx;
}G[maxn<<2];
void add(int u,int v,int id){
G[cnt].to = v;
G[cnt].next = head[u];
G[cnt].idx = id;
head[u] = cnt++;
}
deque<int> q;
void bfs(){
for(int i = head[1];~i;i=G[i].next) dis[i/2] = 1,q.push_back(i/2);
while(!q.empty()){
int now = q.front();
q.pop_front();
for(int i = head[G[now*2].to];~i;i=G[i].next){
if(G[i].idx == G[now*2].idx){
if(dis[i/2] > dis[now]){
dis[i/2] = dis[now];q.push_front(i/2);
}
}else{
if(dis[i/2] > dis[now] + 1){
dis[i/2] = dis[now]+1;q.push_back(i/2);
}
}
}
for(int i = head[G[now*2+1].to];~i;i=G[i].next){
if(G[i].idx == G[now*2+1].idx){
if(dis[i/2] > dis[now]){
dis[i/2] = dis[now];q.push_front(i/2);
}
}else{
if(dis[i/2] > dis[now]+1){
dis[i/2] = dis[now]+1;q.push_back(i/2);
}
}
}
}
ans = INF;
for(int i = head[n];~i;i=G[i].next){
if(ans > dis[i/2]) ans = dis[i/2];
}
}
int main(){
#ifdef LOCAL
freopen("a.in","r",stdin);
#endif
while(~scanf("%d%d",&n,&m)){
memset(head,-1,sizeof(int)*(n+2));cnt = 0;
rep(i,0,m+2) dis[i] = INF;
rep(i,0,m){
int u,v,id;read(u);read(v);read(id);
add(u,v,id);add(v,u,id);
}
bfs();
printf("%d\n",ans==INF?-1:ans);
}
return 0;
}