Submission #66351833

Source Code Expand

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
n,m=map(int,input().split())
edg=[]
banned=[[] for _ in range(30)]
g=[[] for _ in range(n)]
from collections import deque
for i in range(m):
    u,v,w=map(int,input().split())
    u-=1
    v-=1
    g[u].append((v,i))
    g[v].append((u,i))
    edg.append(w)
    for j in range(29,-1,-1):
        if (w>>j)&1:
            banned[j].append(i)
ans=[0]*30
can=set([i for i in range(m)])
for i in range(29,-1,-1):
    tmp=[]
    for nn in banned[i]:
        if nn in can:
 
 
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX

n,m=map(int,input().split())
edg=[]
banned=[[] for _ in range(30)]
g=[[] for _ in range(n)]
from collections import deque
for i in range(m):
    u,v,w=map(int,input().split())
    u-=1
    v-=1
    g[u].append((v,i))
    g[v].append((u,i))
    edg.append(w)
    for j in range(29,-1,-1):
        if (w>>j)&1:
            banned[j].append(i)
ans=[0]*30
can=set([i for i in range(m)])
for i in range(29,-1,-1):
    tmp=[]
    for nn in banned[i]:
        if nn in can:
            can.discard(nn)
            tmp.append(nn)
    que=deque()
    vis=[0]*n
    que.append(0)
    vis[0]=1
    while que:
        now=que.popleft()
        for nxt,num in g[now]:
            if num in can and vis[nxt]==0:
                que.append(nxt)
                vis[nxt]=1
    if vis[-1]==0:
        for nn in tmp:
            can.add(nn)
        ans[i]=1
        continue
a=0
noww=1
for i in range(30):
    a+=ans[i]*noww
    noww<<=1
print(a)

Submission Info

Judge Result