电商商城网站_高清设计网站推荐_seo网络推广培训班_网站排名优化软件哪家好

拓扑排序

卡码网 117. 软件构建
代码随想录

V, E = map(int, input().split())graph = [[-1]* (V+1) for _ in range(V + 1) ]in_degrees = [0] * V
for _ in range(E):s,t = map(int, input().split())graph[s][t] = 1in_degrees[t] += 1zero_queue = []
for i in range(0, V):if in_degrees[i] == 0:zero_queue.append(i)
done_set = []
while zero_queue:node = zero_queue.pop()done_set.append(node)for j in range(0,V):if graph[node][j] == 1:in_degrees[j] -= 1if in_degrees[j] == 0:zero_queue.append(j)if len(done_set) == V:res = ""for item in done_set:res += str(item) + " "print(res.strip())
else:print(-1)

dijkstra（朴素版）

卡码网 47. 参加科学大会
代码随想录

V, E = map(int, input().split())graph = [[-1]* (V+1) for _ in range(V + 1) ]for _ in range(E):s,t,val = map(int, input().split())graph[s][t] = valvisited = set()# 初始化距离
distance = [float("+inf")] * (V+1)
distance[1] = 0node = 1
while True:visited.add(node)# 更新距离：对可达+没有访问过的节点进行操作for i in range(2, V + 1):if i in visited:continueif graph[node][i] == -1:continue# 从起点到node的距离+node到i的距离如果小于起点到i的距离就更新起点到i的距离new_dist = graph[node][i] + distance[node]if new_dist < distance[i]:distance[i] = new_distdis = float("inf")# 找新的节点：遍历距离，找一个距离最小的，没有被访问过的节点。new_node = nodefor i in range(2, V+1):if i in visited:continueif distance[i] < dis:new_node = idis = min(dis, distance[i])# 退出条件if len(visited) == V or new_node == node:break# 新节点node = new_node
print(distance[-1]) if distance[-1] != float("+inf") else print(-1)