首页 > 试题广场 >

小红送外卖

[编程题]小红送外卖
  • 热度指数：1167 时间限制：C/C++ 2秒，其他语言4秒 空间限制：C/C++ 256M，其他语言512M
  • 算法知识视频讲解
\hspace{15pt}学园城共有 n 个结点和 m 条双向道路，其中 1 号结点为 美食街，其余结点均为学校。保证整张图连通。

\hspace{15pt}小红的送餐流程如下：
\hspace{23pt}\bullet\, 从美食街出发前往某所学校送餐；
\hspace{23pt}\bullet\, 抵达后立即骑车返回美食街；
\hspace{15pt}上述流程重复 q 次，第 i 次需前往学校 a_i。请你计算，小红完成全部订单所需骑行距离的最小值。

输入描述:
\hspace{15pt}第一行输入三个整数 n,m,q\ \left(1 \leqq n,m,q \leqq 10^5\right) —— 结点数、道路数和送餐次数。 
\hspace{15pt}接下来 m 行，第 i 行输入三个整数 u_i,v_i,w_i\ \left(1 \leqq u_i,v_i \leqq n;\ u_i \neq v_i;\ 1 \leqq w_i \leqq 10^4\right)，表示一条连接 u_i 与 v_i 的双向道路，其长度为 w_i。 
\hspace{15pt}最后一行输入 q 个整数 a_1,a_2,\dots,a_q\ \left(2 \leqq a_i \leqq n\right)，其中 a_i 表示第 i 次送餐的目的学校。


输出描述:
\hspace{15pt}输出一个整数，代表完成全部订单最少需要骑行的总距离。
示例1

输入

3 2 2
1 2 1
1 3 2
2 3

输出

6

说明

小红先从美食街骑到2号学校，再返回美食街，骑行距离为1+1=2
小红先从美食街骑到3号学校，再返回美食街，骑行距离为2+2=4
因此总共的骑行距离为2+4=6
算法知识视频讲解
开通博客
头像 Mag1c0nch
发表于 2024-11-28 21:15:26
大水题，跑完dijk后就可以得知 1 的其他点的最短路，然后每次乘2即可，因为是来回 #include <bits/stdc++.h> using namespace std; #define int long long const int INF = 1e18; const int N 展开全文
去ta的博客 赞 (3) 回复(0) 收起
头像 阿里嘎多懒羊羊桑_
发表于 2024-11-29 11:31:02
题意小红在第三新北林市的学园城送外卖，学园城中有非常多的学校，学园城里有一个美食街。小红每次会接一些同一个学校的订单，然后从美食街取餐出发，再骑车将外卖送到学校，最后回到美食街，以此往复。学园城有 n 个结点， m 条道路，美食街为1号结点，剩下的结点都是学校，保证学园城中所有结点连通。给出小红每次 展开全文
去ta的博客 赞 (2) 回复(0) 收起
头像 Kato_Shoko
发表于 2024-11-27 17:49:42
来去的路程是一样的，所以只需要跑一遍dijk就可以算出来，然后就可以计算答案了，注意是无向图就行。 #include <iostream> #include <queue> #include <map> #include <set> #include 展开全文
去ta的博客 赞 (1) 回复(0) 收起
头像 龍眠
发表于 2025-05-23 16:55:08
import java.io.*; import java.util.*; public class Main { public static void main(String[] args) throws IOException { BufferedReader br = 展开全文
去ta的博客 赞 (0) 回复(0) 收起
头像 给我中奖吧
发表于 2025-05-21 11:07:02
#include <bits/stdc++.h> using namespace std; const int maxn = 2e6 + 10; typedef pair<long long, long long> PII; int n, m, q; int h[max 展开全文
去ta的博客 赞 (0) 回复(0) 收起
头像 丨阿伟丨
发表于 2025-09-09 15:55:48
题目链接 小红送外卖 题目描述 在一个带权无向图中，给定一个起始点（1号美食街）和 个送餐目的地。对于每个目的地，都需要从起始点出发，送达后再返回起始点。求完成所有 次送餐任务所需的最短总骑行距离。 解题思路 这个问题的核心是计算从一个固定的起点（1号节点）到多个不同目的地的最短往返距离之和。 展开全文
去ta的博客 赞 (0) 回复(0) 收起
头像 是基德吖
发表于 2024-11-29 23:55:08
import java.io.*; import java.util.*; public class Main { static class Edge { int v, w; Edge(int v, int w) { this.v = 展开全文
去ta的博客 赞 (0) 回复(0) 收起
头像 8F76
发表于 2025-05-25 17:41:16
#include <bits/stdc++.h> using namespace std; #define IOS ios::sync_with_stdio(false), cin.tie(0); typedef long long LL; typedef pair<int,in 展开全文
去ta的博客 赞 (0) 回复(0) 收起

问题信息

难度：
5条回答 1085浏览

热门推荐

相关试题

小红送外卖

扫一扫，把题目装进口袋

求职之前，先上牛客

扫描二维码，进入QQ群

扫描二维码，关注牛客公众号