題目:

有了一張自駕旅游路線圖，你會知道城市間的高速公路長度、以及該公路要收取的過路費。現(xiàn)在需要你寫一個程序，幫助前來咨詢的游客找一條出發(fā)地和目的地之間的最短路徑。如果有若干條路徑都是最短的，那么需要輸出最便宜的一條路徑。

輸入格式:
輸入說明：輸入數(shù)據(jù)的第1行給出4個正整數(shù)N、M、S、D，其中N（2≤N≤500）是城市的個數(shù)，順便假設(shè)城市的編號為0~(N?1)；M是高速公路的條數(shù)；S是出發(fā)地的城市編號；D是目的地的城市編號。隨后的M行中，每行給出一條高速公路的信息，分別是：城市1、城市2、高速公路長度、收費額，中間用空格分開，數(shù)字均為整數(shù)且不超過500。輸入保證解的存在。

輸出格式:
在一行里輸出路徑的長度和收費總額，數(shù)字間以空格分隔，輸出結(jié)尾不能有多余空格。

輸入樣例:
4 5 0 3
0 1 1 20
1 3 2 30
0 3 4 10
0 2 2 20
2 3 1 20
輸出樣例:
3 40

代碼及注釋：

#include <stdio.h>
#include <stdlib.h>
#include <stdbool.h>#define MAX_VERTEX_NUM 500
#define MAX_DIST 501
#define MAX_COST 501
#define ERROR -1typedef int Vertex;struct _Edge
{Vertex V, W;int dist, cost;
};
typedef struct _Edge *Edge;struct _MGraph
{int Nv, Ne;int dist[MAX_VERTEX_NUM][MAX_VERTEX_NUM];int cost[MAX_VERTEX_NUM][MAX_VERTEX_NUM];
};
typedef struct _MGraph *MGraph; /* 以鄰接矩陣存儲的圖的類型  */void InsertEdge(MGraph G, Edge E); // 插入邊
MGraph CreateGraph(int vertexNum); // 初始化圖
MGraph BuildGraph();Vertex FindMinDist(MGraph G, int dist[], bool collected[]);
void Dijkstra(MGraph G, int dist[], int cost[], Vertex S);Vertex src, dst;
// 對于全局的int數(shù)組自動初始化為0，bool數(shù)組初始化為false
int dist[MAX_VERTEX_NUM];
int cost[MAX_VERTEX_NUM];
bool collected[MAX_VERTEX_NUM];/*
07-圖6 旅游規(guī)劃
https://pintia.cn/problem-sets/1667128414987735040/exam/problems/1667128415088398337難度：2顆星4 5 0 3
0 1 1 20
1 3 2 30
0 3 4 10
0 2 2 20
2 3 1 203 40*/int main()
{MGraph G = BuildGraph();Dijkstra(G, dist, cost, src);printf("%d %d\n", dist[dst], cost[dst]);free(G);return 0;
}MGraph CreateGraph(int vertexNum)
{MGraph G = (MGraph)malloc(sizeof(struct _MGraph));G->Nv = vertexNum;G->Ne = 0;Vertex V, W;for (V = 0; V < vertexNum; V++){for (W = 0; W < vertexNum; W++){G->dist[V][W] = MAX_DIST;G->cost[V][W] = MAX_COST;}}return G;
}void InsertEdge(MGraph G, Edge E)
{/* 插入邊<V,W> */G->dist[E->V][E->W] = E->dist;G->cost[E->V][E->W] = E->cost;/* 若是無向圖則要反向也插入 */G->dist[E->W][E->V] = E->dist;G->cost[E->W][E->V] = E->cost;
}MGraph BuildGraph()
{MGraph G;Edge E;int Nv, Ne;scanf("%d %d %d %d", &Nv, &Ne, &src, &dst);G = CreateGraph(Nv);if (Ne){G->Ne = Ne;E = (Edge)malloc(sizeof(struct _Edge));for (int i = 0; i < G->Ne; i++){scanf("%d %d %d %d", &E->V, &E->W, &E->dist, &E->cost);InsertEdge(G, E);}free(E);}return G;
}Vertex FindMinDist(MGraph G, int dist[], bool collected[])
{ /* 返回未被收錄頂點中dist最小者 */Vertex minV = ERROR;int minDist = MAX_DIST;for (Vertex V = 0; V < G->Nv; V++){if (collected[V] == false && minDist > dist[V]){/* 若V未被收錄，且dist[V]更小 */minDist = dist[V]; /* 更新最小距離 */minV = V;          /* 更新對應(yīng)頂點 */}}if (minDist < MAX_DIST) /* 若找到最小dist */return minV;        /* 返回對應(yīng)的頂點下標(biāo) */elsereturn ERROR; /* 若這樣的頂點不存在，返回錯誤標(biāo)記 */
}void Dijkstra(MGraph G, int dist[], int cost[], Vertex S)
{Vertex V, W;/* 初始化：此處默認(rèn)鄰接矩陣中不存在的邊用INFINITY表示 */for (V = 0; V < G->Nv; V++){dist[V] = G->dist[S][V];cost[V] = G->cost[S][V];}/* 先將起點收入集合 */dist[S] = 0;cost[S] = 0;collected[S] = true;while (1){/* V = 未被收錄頂點中dist最小者 */V = FindMinDist(G, dist, collected);if (V == ERROR)      /* 若這樣的V不存在 */break;           /* 算法結(jié)束 */collected[V] = true; /* 收錄V */for (W = 0; W < G->Nv; W++) /* 對圖中的每個頂點W *//* 若W是V的鄰接點并且未被收錄 */if (collected[W] == false && G->dist[V][W] < MAX_DIST){if (G->dist[V][W] < 0) /* 若有負(fù)邊 */return;            /* 不能正確解決，返回錯誤標(biāo)記 *//* 若收錄V使得dist[W]變小 */if (dist[V] + G->dist[V][W] < dist[W]){dist[W] = dist[V] + G->dist[V][W]; /* 更新dist[W] */cost[W] = cost[V] + G->cost[V][W];}else if (dist[V] + G->dist[V][W] == dist[W] &&cost[V] + G->cost[V][W] < cost[W]){cost[W] = cost[V] + G->cost[V][W];}}} /* while結(jié)束*/
}

ChatGPT對代碼的分析，評估：

定義了合適的常量：MAX_DIST 和 MAX_COST 的定義符合題目要求，對于表示距離和花費的最大值都設(shè)置為 501，有效地區(qū)分了有限距離和無窮遠(yuǎn)的情況。

創(chuàng)建圖和插入邊：CreateGraph 和 InsertEdge 函數(shù)用于創(chuàng)建圖和插入邊的操作，實現(xiàn)了初始化圖的鄰接矩陣并向圖中添加邊的功能。

構(gòu)建圖：BuildGraph 函數(shù)根據(jù)輸入構(gòu)建了圖，并通過調(diào)用 CreateGraph 和 InsertEdge 來創(chuàng)建和填充圖的鄰接矩陣。

Dijkstra 算法：Dijkstra 函數(shù)使用 Dijkstra 算法，根據(jù)圖的鄰接矩陣計算從起點到每個頂點的最短距離和最小花費。在這個過程中，使用了輔助函數(shù) FindMinDist 來選擇未被收錄頂點中距離最小的頂點。

主函數(shù)運行：主函數(shù)中先調(diào)用 BuildGraph 構(gòu)建圖，然后調(diào)用 Dijkstra 計算最短距離和最小花費，并輸出結(jié)果。

執(zhí)行結(jié)果：