C语言。小哥从快递站接了一批包裹,他要把每个包裹送到客户手中,并回到快递站交差。显然他希望尽量少跑些路,本题并不要求找出最短的线路,尽量短一点就好。假设快递站和包裹要送到的地方都用编号表示,快递站在 1号,某些地点之间有道路相连,道路的长度已知。请为小哥设计一个送包裹的线路。输入格式 输入的第 1行是两个整数,前一个数表示 n 的值,是包括出快递站在内的地点的数量后一个表示 m,即共有多少条道路。从第 2 行开始,每一行是 3 个正整数,用逗号分隔,形如“x,,z”,表示两个地点之间道路长度,x 和y是地点编号,z 是长度。所有道路信息按首个地点x 升序排列,x 相同者再按V排序。 输出格式 分两行显示,第一行是若干正整数的序列,用空格分隔,表示从快递站(1 号地点)出发,依次到达哪些地点,最后回到快递站。第 2 行一个正整数,表示行走的总长度。 C语言编码
时间: 2023-11-02 08:04:54 浏览: 40
```c
#include <stdio.h>
#include <stdlib.h>
#define MAXN 1005
#define INF 0x3f3f3f3f
int n, m; // n表示点的个数,m表示边的个数
int graph[MAXN][MAXN]; // 存储图的邻接矩阵
int visited[MAXN]; // 存储访问过的点
int path[MAXN]; // 存储路径
int dist[MAXN]; // 存储到起点的距离
// Dijkstra算法求最短路径
void Dijkstra(int start)
{
// 初始化
for(int i = 1; i <= n; i++)
{
visited[i] = 0;
dist[i] = INF;
}
dist[start] = 0;
path[1] = start;
// 依次找到最短距离的点
for(int i = 1; i <= n; i++)
{
int u = -1;
int min_dist = INF;
for(int j = 1; j <= n; j++)
{
if(!visited[j] && dist[j] < min_dist)
{
u = j;
min_dist = dist[j];
}
}
if(u == -1) break; // 如果所有点都已经找到了最短路径,则退出
visited[u] = 1;
// 更新与u相邻的点的最短路径
for(int v = 1; v <= n; v++)
{
if(!visited[v] && graph[u][v] != INF && dist[u] + graph[u][v] < dist[v])
{
dist[v] = dist[u] + graph[u][v];
path[i+1] = v;
}
}
}
}
int main()
{
scanf("%d%d", &n, &m);
// 初始化邻接矩阵
for(int i = 1; i <= n; i++)
{
for(int j = 1; j <= n; j++)
{
if(i == j) graph[i][j] = 0;
else graph[i][j] = INF;
}
}
// 读入边的信息并构建邻接矩阵
for(int i = 1; i <= m; i++)
{
int u, v, w;
scanf("%d,%d,%d", &u, &v, &w);
graph[u][v] = w;
graph[v][u] = w;
}
Dijkstra(1);
// 输出路径
for(int i = 1; i <= n; i++)
{
printf("%d ", path[i]);
}
printf("1\n"); // 最后回到起点
// 输出总长度
printf("%d\n", dist[1]);
return 0;
}
```