首页 > 试题广场 >

小红送外卖

[编程题]小红送外卖

热度指数：188 时间限制：C/C++ 2秒，其他语言4秒空间限制：C/C++ 256M，其他语言512M
算法知识视频讲解

小红在第三新北林市的学园城送外卖，学园城中有非常多的学校，学园城里有一个美食街。小红每次会接一些同一个学校的订单，然后从美食街取餐出发，再骑车将外卖送到学校，最后回到美食街，以此往复。

学园城有 $n$ 个结点， $m$ 条道路，美食街为1号结点，剩下的结点都是学校，保证学园城中所有结点连通。给出小红每次要送外卖的学校，请计算小红最少需要骑行的距离。

输入描述:

第一行输入三个整数  ，分别表示结点数、道路数、送外卖次数。

接下来  行，每行输入三个整数  表示结点  和  之间有一条长度为  的道路。

最后一行输入  个整数表示每次送外卖的学校  。

输出描述:

输出一个整数表示答案。

示例1

输入

输出

说明

小红先从美食街骑到2号学校，再返回美食街，骑行距离为1+1=2
小红先从美食街骑到3号学校，再返回美食街，骑行距离为2+2=4
因此总共的骑行距离为2+4=6

算法知识视频讲解

Hasity学不会

堆优化的迪杰斯特拉算法求距离。

import sys
from collections import defaultdict
from heapq import *
h = defaultdict(list)
n, m, q = map(int, input().split())
st = [0] * (n + 1)
dist = [10**10] * (n + 1)
for _ in range(m):
    a, b, w = map(int, input().split())
    h[a].append([b, w])
    h[b].append([a, w])
# 堆优化的迪杰斯特拉算法，时间复杂度O(mlogn)
q = []
dist[1] = 0
heappush(q, [0, 1])
while q:
    d, a = q[0]
    heappop(q)
    if st[a]:
        continue
    st[a] = 1
    for b, w in h[a]:
        if not st[b] and(dist[b] > dist[a] + w):
            dist[b] = dist[a] + w
            heappush(q, [dist[a] + w, b])


res = 0
a = list(map(int, input().split()))
for b in a:
    res += dist[b] * 2
print(res)

编辑于 2024-03-16 14:40:46 回复(0)