Find the distances from vertex 1 for all vertices in the search, and output 0 for even-numbered vertices and 1 for odd-numbered vertices.
N = int(input())
link = [[] for _ in range(N)]
for _ in range(N - 1):
u, v, w = map(int, input().split())
link[u - 1].append((v - 1, w))
link[v - 1].append((u - 1, w))
d = [-1] * N
d[0] = 0
q = [0]
while q:
p = q.pop()
for n, w in link[p]:
if d[n] == -1:
d[n] = d[p] + w
q.append(n)
for i in d:
print(i % 2)
"A X i </ sub> </ sub> + A Y i </ sub> </ sub> + Z i </ sub> is an even number "." Means that if you know one A, you know the other. If "A X </ sub> + A Y </ sub> + Z i </ "sub> is an even number." And "A X </ sub> + A Z </ sub> + Z j </ sub> is an even number." If you know one of the A's, you know the other two.
Then the question is how many groups A have no relation to each other, and the problem can be reduced to just counting the number of groups with Union Find.
from sys import setrecursionlimit
def find(parent, i):
t = parent[i]
if t < 0:
return i
t = find(parent, t)
parent[i] = t
return t
def unite(parent, i, j):
i = find(parent, i)
j = find(parent, j)
if i == j:
return
parent[j] += parent[i]
parent[i] = j
setrecursionlimit(10 ** 5)
N, M = map(int, input().split())
parent = [-1] * N
for _ in range(M):
X, Y, Z = map(int, input().split())
unite(parent, X - 1, Y - 1)
print(len([x for x in parent if x < 0]))
Just walk and teleport in order, and visit with the one with the least increase in fatigue. Easy.
N, A, B = map(int, input().split())
X = list(map(int, input().split()))
result = 0
for i in range(N - 1):
result += min(A * (X[i + 1] - X[i]), B)
print(result)
For all numbers except -1 and 1, we just add the magical power needed to change it to 1, but there are cases where it requires less magical power to go through another number than to change it directly to 1. , Find the minimum magical power to change each number to 1 by the Worshall Floyd method.
def warshall_floyd(n, d):
for i in range(n):
for j in range(n):
for k in range(n):
d[j][k] = min(d[j][k], d[j][i] + d[i][k])
H, W = map(int, input().split())
N = 10
d = [None] * N
for i in range(N):
d[i] = list(map(int, input().split()))
warshall_floyd(N, d)
m = [d[i][1] for i in range(N)]
result = 0
for _ in range(H):
for i in map(int, input().split()):
if i == -1:
continue
result += m[i]
print(result)
Only the sword with the maximum damage can be swung. No sword with less damage than this swinging damage is required. If the damage is thrown in descending order and the damage exceeds H before reaching the maximum damage to be swung. There is no need to shake. If there is not enough, shake it by that amount. If the sword to be shaken is in the sword to be thrown, if you throw it after shaking, the number of times will be the same, so there is no problem.
N, H = map(int, input().split())
a, b = zip(*(map(int, input().split()) for _ in range(N)))
a_max = max(a) #Maximum damage of shaking
b = [x for x in b if x > a_max] #A sword whose throwing damage is lower than the maximum damage of swinging is meaningless to throw, so remove it
b.sort(reverse=True)
result = 0
#Throw swords in descending order of damage, and if you can defeat them before the sword runs out, that's it.
for x in b:
result += 1
H -= x
if H <= 0:
break
#If you can't defeat it just by throwing it, swing the sword with the maximum damage.
#If the sword with the maximum damage to swing is in the sword to be thrown, it means that it was thrown after swinging as much as necessary
if H > 0:
result += (H + (a_max - 1)) // a_max
print(result)
Recommended Posts