头像

机械佬也想学编程


访客:710

离线:2天前



MAXDIST = float("inf")

n, m, k = map(int, input().split())

side = []
d = [MAXDIST] * (n+10)

def bellman_ford():
    d[1] = 0
    for _ in range(k): # 循环k次,表示走过k条边
        backup = d[:]   # 备份下面这次循环前所有点的距离,确保下面完成一次循环只更新一层点的距离
        for (x, y, z) in side: # 更新所有的边
            d[y] = min(d[y], backup[x] + z)
    if d[n] >= MAXDIST / 2:
        return "impossible"
    else:
        return d[n]


for _ in range(m):
    x, y, z = map(int, input().split())
    side.append((x,y,z))
print(bellman_ford())




import heapq
N = 150010
MAXDIST = float("inf")

n, m = map(int, input().split())

h = [-1] * N #x->y中的x
e = [0] *  N #x->y中的y
w = [-1] * N #x->y的距离
ne = [0] * N
idx = 0

st = [False] * N
d = [MAXDIST] * N

q = []

def dijkstra():
    d[1] = 0
    heapq.heappush(q, (0, 1))
    while q:
        distance, i = heapq.heappop(q)
        if st[i]:
            continue
        st[i] = True
        k = h[i]
        while k != -1:
            j = e[k]
            if d[j] > d[i]+w[k]:
                d[j] = d[i]+w[k]
                heapq.heappush(q, (d[j], j))
            k = ne[k]

    if d[n] >= MAXDIST:
        return -1
    else:
        return d[n]


def add(x, y, z):
    global idx
    e[idx] = y
    w[idx] = z
    ne[idx] = h[x]
    h[x] = idx
    idx += 1



for _ in range(m):
    x, y, z = map(int, input().split())
    add(x, y, z)
print(dijkstra())



n, m = map(int, input().split())
maxdist = float("inf")
g = [[maxdist] * (n+1) for _ in range(n+1)] # 由于是密集图,m>>n,因此用邻接矩阵来存储,g[x][y]表示x指向y的距离
d = [maxdist] * (n+1) # 存储每个点距离起点的距离,初始化为距离最大,d[1]=0
st = [False] * (n+1) # 判断某一点的最短距离是否已经确定,False表示未确定,True表示确定

def dijkstra():
    d[1] = 0
    for i in range(1, n+1): # 因为要确定n个点的最短路,因此要循环n次
        t = -1
        for j in range(1, n+1): # 每次找到还未确定最短路的点中距离起点最短的点t
            if not st[j] and (t==-1 or d[t]>d[j]):
                t = j
        st[t] = True
        for j in range(1, n+1): # 用t来更新t所指向的点的距离
            d[j] = min(d[j], d[t] + g[t][j])
    if d[n] >= maxdist:
        return -1
    else:
        return d[n]

for _ in range(m):
    x, y, z = map(int, input().split())
    g[x][y] = min(g[x][y], z) # 当出现重边时,只需取两个距离中的最小值
print(dijkstra())



n, m = map(int, input().split())
maxdist = 10010
g = [[maxdist] * (n+1) for _ in range(n+1)] # 由于是密集图,m>>n,因此用邻接矩阵来存储,g[x][y]表示x指向y的距离
d = [maxdist] * (n+1) # 存储每个点距离起点的距离,初始化为距离最大,d[1]=0
st = [False] * (n+1) # 判断某一点的最短距离是否已经确定,False表示未确定,True表示确定

def dijkstra():
    d[1] = 0
    for i in range(1, n+1): # 因为要确定n个点的最短路,因此要循环n次
        t = -1
        for j in range(1, n+1): # 每次找到还未确定最短路的点中距离起点最短的点t
            if not st[j] and (t==-1 or d[t]>d[j]):
                t = j
        st[t] = True
        for j in range(1, n+1): # 用t来更新t所指向的点的距离
            d[j] = min(d[j], d[t] + g[t][j])
    if d[n] >= 10010:
        return -1
    else:
        return d[n]

for _ in range(m):
    x, y, z = map(int, input().split())
    g[x][y] = min(g[x][y], z) # 当出现重边时,只需取两个距离中的最小值
print(dijkstra())



n, m = map(int, input().split())

N = 10**5 + 10
h = [-1] * N
e = [0] * N
ne = [0] * N
idx = 0

q = [0] * N
d = [0] * N

def topsort():
    hh, tt = 0, -1
    for i in range(1, n+1):
        if d[i] == 0:
            tt += 1
            q[tt] = i
    while hh <= tt:
        k = q[hh]
        hh += 1
        j = h[k]
        while j != -1:
            val = e[j]
            j = ne[j]
            d[val] -= 1
            if d[val] == 0:
                tt += 1
                q[tt] = val
    return tt == n-1

def add(a, b):
    global idx 
    e[idx] = b
    ne[idx] = h[a]
    h[a] = idx
    idx += 1
    d[b] += 1 # 表示b点前面有几个点指向b


for _ in range(m):
    a, b = map(int, input().split())
    add(a, b)
if topsort():
    for i in range(n):
        print(q[i], end=" ")
else:
    print(-1)


活动打卡代码 AcWing 847. 图中点的层次

n, m = map(int, input().split())
N = 10 ** 5 + 10


h = [-1] * N
e = [0] * N
ne = [0] * N
idx = 0

q = [0] * N
d = [-1] * N
d[1] = 0

def bfs():
    hh, tt = 0, 0
    q[hh] = 1
    while hh <= tt:
        k = q[hh]
        hh += 1
        p = h[k]
        while p != -1:
            val = e[p]
            p = ne[p]
            if d[val] == -1:
                d[val] = d[k] + 1
                tt += 1
                q[tt] = val
    return d[n]

def add(a, b):
    global idx
    e[idx] = b
    ne[idx] = h[a]
    h[a] = idx
    idx += 1


for _ in range(m):
    a, b = map(int, input().split())
    add(a, b)
print(bfs())


活动打卡代码 AcWing 845. 八数码

from collections import deque


def bfs(start):
    end = "12345678x"
    d = {start : 0} # 该字典存放每个状态距离初始状态的距离
    q = deque() # 存放将要验证的状态
    q.append(start)
    dx = [0, 1, 0, -1] # 用于"x"上下左右移动
    dy = [1, 0, -1, 0]
    while q:
        t = q.popleft()
        distance = d[t]
        if t == end:
            return distance
        k = t.index('x')
        x = k // 3 # 字符串的索引转换成3x3矩阵后的坐标
        y = k % 3

        tl = list(t) # 由于字符串不是不可变量,因而把字符串变为数组,用于交换字符串中的字符位置
        for i in range(4): # "x"上下左右移动
            a = x + dx[i]
            b = y + dy[i]
            if a >=0 and a < 3 and b >=0 and b < 3: # 若坐标未超出矩阵范围
                nk = a * 3 + b #3x3矩阵的坐标转换成字符串的索引
                tl[nk], tl[k] = tl[k], tl[nk] # 交换字符串中的字符位置
                t = "".join(tl)
                if t not in d: # 如果t这个状态是新状态(之前未出现过)
                    q.append(t)
                    d[t] = distance + 1
                tl[nk], tl[k] = tl[k], tl[nk] # 还原现场
    return -1



start = input().replace(" ", "")
ans = bfs(start)
print(ans)



from collections import deque


def bfs(start):
    end = "12345678x"
    d = {start : 0} # 该字典存放每个状态距离初始状态的距离
    q = deque() # 存放将要验证的状态
    q.append(start)
    dx = [0, 1, 0, -1] # 用于"x"上下左右移动
    dy = [1, 0, -1, 0]
    while q:
        t = q.popleft()
        distance = d[t]
        if t == end:
            return distance
        k = t.index('x')
        x = k // 3 # 字符串的索引转换成3x3矩阵后的坐标
        y = k % 3

        tl = list(t) # 由于字符串不是不可变量,因而把字符串变为数组,用于交换字符串中的字符位置
        for i in range(4): # "x"上下左右移动
            a = x + dx[i]
            b = y + dy[i]
            if a >=0 and a < 3 and b >=0 and b < 3: # 若坐标未超出矩阵范围
                nk = a * 3 + b #3x3矩阵的坐标转换成字符串的索引
                tl[nk], tl[k] = tl[k], tl[nk] # 交换字符串中的字符位置
                t = "".join(tl)
                if t not in d: # 如果t这个状态是新状态(之前未出现过)
                    q.append(t)
                    d[t] = distance + 1
                tl[nk], tl[k] = tl[k], tl[nk] # 还原现场
    return -1



start = input().replace(" ", "")
ans = bfs(start)
print(ans)



N = 10**5 + 10
ans = N
st = [False] * N
h = [-1] * N
e = [0] * 2 * N
ne = [0] * 2 * N
idx = 0

# 返回以x为根结点的树总共的节点数
def dfs(x):
    global ans
    st[x] = True # 标记x点已经搜寻过了
    sum = 1
    size = 0
    i = h[x]
    while i != -1: # 遍历x节点的子节点
        val = e[i]
        i = ne[i]
        if not st[val]:
            s = dfs(val) # 返回以val为根结点的子树节点数
            sum += s
            size = max(size, s)

    size = max(size, n-sum)
    ans = min(size, ans)
    return sum

# 把b添加到a的子节点中
def add(a, b):
    global idx
    e[idx] = b
    ne[idx] = h[a]
    h[a] = idx
    idx += 1

n = int(input())
for _ in range(n-1):
    a, b = map(int, input().split())
    add(a, b) # 由于是无向边,因此要分别添加两者
    add(b, a)
dfs(1) # 随便从哪个节点开始都可以
print(ans)


活动打卡代码 AcWing 846. 树的重心

N = 10**5 + 10
ans = N
st = [False] * N
h = [-1] * N
e = [0] * 2 * N
ne = [0] * 2 * N
idx = 0

# 返回以x为根结点的树总共的节点数
def dfs(x):
    global ans
    st[x] = True # 标记x点已经搜寻过了
    sum = 1
    size = 0
    i = h[x]
    while i != -1: # 遍历x节点的子节点
        val = e[i]
        i = ne[i]
        if not st[val]:
            s = dfs(val) # 返回以val为根结点的子树节点数
            sum += s
            size = max(size, s)

    size = max(size, n-sum)
    ans = min(size, ans)
    return sum

# 把b添加到a的子节点中
def add(a, b):
    global idx
    e[idx] = b
    ne[idx] = h[a]
    h[a] = idx
    idx += 1

n = int(input())
for _ in range(n-1):
    a, b = map(int, input().split())
    add(a, b) # 由于是无向边,因此要分别添加两者
    add(b, a)
dfs(1) # 随便从哪个节点开始都可以
print(ans)