互联网推广公司,北京网站怎么优化,c2c网站开发策划,wordpress is sticky作为一个城市的应急救援队伍的负责人#xff0c;你有一张特殊的全国地图。在地图上显示有多个分散的城市和一些连接城市的快速道路。每个城市的救援队数量和每一条连接两个城市的快速道路长度都标在地图上。当其他城市有紧急求助电话给你的时候#xff0c;你的任务是带领你的…作为一个城市的应急救援队伍的负责人你有一张特殊的全国地图。在地图上显示有多个分散的城市和一些连接城市的快速道路。每个城市的救援队数量和每一条连接两个城市的快速道路长度都标在地图上。当其他城市有紧急求助电话给你的时候你的任务是带领你的救援队尽快赶往事发地同时一路上召集尽可能多的救援队。
输入格式:
输入第一行给出4个正整数N、M、S、D其中N2≤N≤500是城市的个数顺便假设城市的编号为0 ~ (N−1)M是快速道路的条数S是出发地的城市编号D是目的地的城市编号。
第二行给出N个正整数其中第i个数是第i个城市的救援队的数目数字间以空格分隔。随后的M行中每行给出一条快速道路的信息分别是城市1、城市2、快速道路的长度中间用空格分开数字均为整数且不超过500。输入保证救援可行且最优解唯一。
输出格式:
第一行输出最短路径的条数和能够召集的最多的救援队数量。第二行输出从S到D的路径中经过的城市编号。数字间以空格分隔输出结尾不能有多余空格。
输入样例:
4 5 0 3
20 30 40 10
0 1 1
1 3 2
0 3 3
0 2 2
2 3 2输出样例:
2 60
0 1 3
分析
首先代码从标准输入读取节点数 n边数 m源点 s 和终点 d。接着读取每个节点的帮助值并建立节点和其对应邻居的边这里边是有向的每个边都连接两个节点并有一个相关的权重。然后初始化一个距离数组 dist用于存储从源点 s 到每个节点的最短距离。同时初始化两个累计数组 total 和 sum_help用于存储从源点 s 到每个节点的所有节点的帮助值的总和。还初始化一个 parent 数组用于存储最短路径上的节点。使用堆优先队列q 存储待处理的节点。将源点 s 添加到堆中并设置其距离为 0总帮助值为 1累计帮助值为其自身的帮助值。然后进入一个 while 循环不断地从堆中取出距离最小的节点并更新其邻居的距离和累计帮助值。如果邻居的距离更新那么就将其添加到堆中。当堆为空时结束循环。此时dist 和 total 数组中存储的值就是从源点 s 到每个节点的最短距离和累计帮助值。最后通过回溯 parent 数组找出从源点 s 到终点 d 的最短路径并打印出来。同时打印出终点的累计帮助值。
Python版本
import heapq
import sysn, m, s, d map(int, sys.stdin.readline().split())
help_val list(map(int, sys.stdin.readline().split()))
edge [[] for _ in range(n)]
for _ in range(m):x, y, z map(int, sys.stdin.readline().split())edge[x].append((y, z))edge[y].append((x, z))dist [float(inf) for _ in range(n)]
total [0 for _ in range(n)]
sum_help [0 for _ in range(n)]
p [-1 for _ in range(n)]
dist[s] 0
total[s] 1
sum_help[s] help_val[s]
q []
heapq.heappush(q, (0, s))while q:tmp heapq.heappop(q)x tmp[1]if dist[x] tmp[0]:continuefor i in edge[x]:if dist[i[0]] dist[x] i[1]:dist[i[0]] dist[x] i[1]total[i[0]] total[x]sum_help[i[0]] sum_help[x] help_val[i[0]]p[i[0]] xheapq.heappush(q, (dist[i[0]], i[0]))else:if dist[i[0]] dist[x] i[1]:total[i[0]] total[x]sum_help_tmp sum_help[x] help_val[i[0]]if sum_help_tmp sum_help[i[0]]:sum_help[i[0]] sum_help_tmpp[i[0]] xpath []
x d
while x ! -1:path.append(str(x))x p[x]
print(total[d], sum_help[d])
print( .join(path[::-1]))总结 这段代码的主要创新点在于同时求解最短路径和累计帮助值。这在一些实际的网络优化问题中是非常有用的。例如在紧急救援中我们需要找出一条最短的路线同时还要考虑沿途各个节点的资源如食物、水等的总量。
