C语言。小哥从快递站接了一批包裹,他要把每个包裹送到客户手中,并回到快递站交差。显然他希望尽量少跑些路,本题并不要求找出最短的线路,尽量短一点就好。假设快递站和包裹要送到的地方都用编号表示,快递站在 1号,某些地点之间有道路相连,道路的长度已知。请为小哥设计一个送包裹的线路。输入格式 输入的第 1行是两个整数,前一个数表示 n 的值,是包括出快递站在内的地点的数量后一个表示 m,即共有多少条道路。从第 2 行开始,每一行是 3 个正整数,用逗号分隔,形如“x,,z”,表示两个地点之间道路长度,x 和y是地点编号,z 是长度。所有道路信息按首个地点x 升序排列,x 相同者再按V排序。 输出格式 分两行显示,第一行是若干正整数的序列,用空格分隔,表示从快递站(1 号地点)出发,依次到达哪些地点,最后回到快递站。第 2 行一个正整数,表示行走的总长度。 C语言编码
时间: 2023-11-02 14:04:54 浏览: 28
```c
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#define MAX_N 1005
#define MAX_M 20005
typedef struct {
int x, y, z;
} Edge;
Edge edges[MAX_M];
int n, m, cnt;
int head[MAX_N], dist[MAX_N], vis[MAX_N], path[MAX_N];
void add(int x, int y, int z) {
edges[++cnt].x = x;
edges[cnt].y = y;
edges[cnt].z = z;
edges[cnt].next = head[x];
head[x] = cnt;
}
void spfa() {
memset(dist, 0x3f, sizeof(dist));
memset(vis, 0, sizeof(vis));
memset(path, -1, sizeof(path));
int q[MAX_N * 10];
int hh = 0, tt = 1;
q[0] = 1;
dist[1] = 0;
vis[1] = 1;
while (hh != tt) {
int t = q[hh++];
if (hh == MAX_N * 10) hh = 0;
vis[t] = 0;
for (int i = head[t]; i != -1; i = edges[i].next) {
int y = edges[i].y, z = edges[i].z;
if (dist[y] > dist[t] + z) {
dist[y] = dist[t] + z;
path[y] = t;
if (!vis[y]) {
vis[y] = 1;
q[tt++] = y;
if (tt == MAX_N * 10) tt = 0;
}
}
}
}
}
int main() {
memset(head, -1, sizeof(head));
scanf("%d%d", &n, &m);
for (int i = 1; i <= m; i++) {
int x, y, z;
scanf("%d%d%d", &x, &y, &z);
add(x, y, z);
add(y, x, z);
}
spfa();
int idx = 1;
while (path[idx] != -1) {
printf("%d ", idx);
idx = path[idx];
}
printf("1\n");
printf("%d\n", dist[1]);
return 0;
}
```