题目描述
春节到了，小从要给亲戚送年货，一直小从在编号为1的位置，他一共给n-1家亲戚送年货，由于每家要给的东西较多，所以每送一家，小从都需要回家再拿一份年货。现在我们给每家亲戚编号为2—n, 这些亲戚直接有m条道路相连，每条道路的距离为s。请你帮小从计算一些，送完所有年货，他一共要走多少路。
输入格式
第一行包含两个这个数n和m，（1
输出格式
一个整数，表示小童走的路程。
样例
样例输入
5 7 1
1 2 2
1 3 4
1 4 7
2 3 1
2 5 2
3 4 1
3 5 6
样例输出
26
在这道题目中，你需要输出一个整数，表示小从送完所有年货后走的路程。
为了解决这个问题，你需要在程序中先读入数据，然后计算小从送完所有年货后走的路程，最后输出结果即可。
你可以使用 cout 来输出结果，例如：
cout << "小从走的路程是：" << distance << endl;
其中，distance 是计算出来的路程，endl 是换行符。
你也可以使用 printf 来输出结果，例如：
printf("小从走的路程是：%d\n", distance);
其中，%d 是一个占位符，表示输出一个整数，\n 是换行符。
无论使用哪种方法，在最后都要记得加上换行符，以便输出多个结果。
希望这些信息能帮到你！
各种格式都有
https://blog.csdn.net/qq_62654838/article/details/127036071
1、建立一张有向图，并使用邻接表存储，邻接表存储方式如下：
struct Edge
{
int v, w, next;
} edges[MAX_M];
int head[MAX_N], edge_cnt;
2、对于每一个输入的点，将边加入到邻接表中
void add_edge(int u, int v, int w)
{
edges[edge_cnt].v = v;
edges[edge_cnt].w = w;
edges[edge_cnt].next = head[u];
head[u] = edge_cnt++;
}
3、对于1号点，找到所有的出边，对于每一条出边，都从1号点出发，走到对应的点，并统计总的距离
int dfs(int u)
{
int distance = 0;
for (int i = head[u]; i != -1; i = edges[i].next)
{
int v = edges[i].v;
int w = edges[i].w;
distance += w + dfs(v);
}
return distance;
}
4、最后调用dfs函数，并将结果输出即可
int main()
{
// 初始化邻接表
memset(head, -1, sizeof(head));
// 读入数据
int n, m;
cin >> n >> m;
for (int i = 0; i < m; i++)
{
int u, v, w;
cin >> u >> v >> w;
add_edge(u, v, w);
}
// 调用dfs函数并输出结果
cout << dfs(1) << endl;
return 0;
}
仅供参考，望采纳，谢谢。
```c++
#include<iostream>
#include<algorithm>
#include<cstring>
#include<queue>
#define x first
#define y second
using namespace std;
const int N=35;
typedef pair<int,int> PII;
int n,m,s,h[N],e[N2],ne[N2],idx,t[N],dis[N];
bool st[N];
void add(int a,int b,int c){
e[idx]=b,t[idx]=c,ne[idx]=h[a],h[a]=idx++;
}
int dijkstra(){
memset(dis,0x3f,sizeof dis);
priority_queue<PII,vector<PII>,greater<PII>> q;
q.push({0,1});
dis[1]=0;
while(q.size()){
PII t=q.top();
q.pop();
int ver=t.y;
if(st[ver]) continue;
st[ver]=true;
for(int i=h[ver];~i;i=ne[i]){
int j=e[i];
if(dis[j]>dis[ver]+t[i]){
dis[j]=dis[ver]+t[i];
q.push({dis[j],j});
}
}
}
int res=0;
for(int i=2;i<=n;i++){
res+=dis[i]*2;
}
return res;
}
int main(){
scanf("%d%d",&n,&m);
memset(h,-1,sizeof h);
while(m--){
int a,b,c;
scanf("%d%d%d",&a,&b,&c);
add(a,b,c),add(b,a,c);
}
cout<<dijkstra();
return 0;
}
```
解题思路
本题是一道求最短路径的题目。
首先根据题目描述，我们可以将每条边抽象成一个结点，每个结点都有一个权值，表示这条边的距离。
然后我们可以使用深度优先搜索的方法，从编号为1的结点开始，按照题目所给的边的连接情况，依次遍历每个结点。
当遍历完所有结点后，我们就可以统计出遍历所有结点所需要走的最短路径。
下面是Java代码实现：
import java.util.*;
public class Main {
static int n, m;
static int[][] e;
static boolean[] v;
static int ans;
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
n = sc.nextInt();
m = sc.nextInt();
e = new int[n + 1][n + 1];
v = new boolean[n + 1];
for (int i = 1; i <= m; i++) {
int a = sc.nextInt();
int b = sc.nextInt();
int s = sc.nextInt();
e[a][b] = s;
e[b][a] = s;
}
v[1] = true;
dfs(1, 0);
System.out.println(ans);
}
public static void dfs(int u, int sum) {
if (u == n) {
ans = Math.min(ans, sum);
return;
}
for (int i = 1; i <= n; i++) {
if (e[u][i] != 0 && !v[i]) {
v[i] = true;
dfs(i, sum + e[u][i]);
v[i] = false;
}
}
}
}
可以使用深度优先搜索来实现这个功能。首先，你需要一个函数来递归搜索所有路径。该函数接受当前节点和当前路径长度作为参数。然后，你可以遍历所有与当前节点相连的边，并递归调用函数搜索下一个节点，参考：
#include <iostream>
using namespace std;
const int N = 35;
int n, m;
int edges[N][3];
int findPaths(int node, int length) {
for (int i = 0; i < m; i++) {
int x = edges[i][0];
int y = edges[i][1];
int s = edges[i][2];
// 如果当前边从当前节点开始
if (x == node) {
// 递归搜索下一个节点
length += s + findPaths(y, 0);
}
}
return length;
}
int main() {
cin >> n >> m;
// 读入边的信息
for (int i = 0; i < m; i++) {
cin >> edges[i][0] >> edges[i][1] >> edges[i][2];
}
// 从节点1开始查找路径
int length = findPaths(1, 0);
cout << length << endl;
return 0;
}
#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;
const int N = 50;
int n, m;
int g[N][N]; // 邻接矩阵存图
int dis[N]; // 存储每个点到1号点的距离
bool st[N]; // 判断每个点是否已经确定了最短路
// 迪杰斯特拉算法
void dijkstra(int u)
{
memset(dis, 0x3f, sizeof dis); // 初始化所有点到1号点的距离为正无穷
dis[u] = 0; // 1号点到自己的距离为0
for (int i = 0; i < n - 1; i ++ ) // 最多循环n-1次，每次找到一个点
{
int t = -1;
for (int j = 1; j <= n; j ++ ) // 找到离1号点距离最短的点
if (!st[j] && (t == -1 || dis[t] > dis[j])) t = j; // t是找到的点的编号
st[t] = true; // 标记这个点已经确定了最短路
for (int j = 1; j <= n; j ++ ) // 更新以t为中间点的最短路
dis[j] = min(dis[j], dis[t] + g[t][j]); // 取较短的距离
}
}
int main()
{
cin >> n >> m;
memset(g, 0x3f, sizeof g); // 初始化所有边的距离为正无穷
while (m -- )
{
int a, b, s;
cin >> a >> b >> s;
g[a][b] = g[b][a] = s; // 因为图是无向图，所以a到b和b到a的距离都是s
}
dijkstra(1);
int res = 0;
for (int i = 2; i <= n; i ++ ) res += dis[i]; // 累加所有点到1号点的距离
cout << res << endl;
return 0;
}