1.旅游规划
有了一张自驾旅游路线图，你会知道城市间的高速公路长度、以及该公路要收取的过路费。现在需要你写一个程序，帮助前来咨询的游客找一条出发地和目的地之间的最短路径。如果有若干条路径都是最短的，那么需要输出最便宜的一条路径。
时间限制：1000
内存限制：65536
输入
输入说明：输入数据的第 1 行给出 4 个正整数 n、m、s、d，其中 n（2 ≤ n ≤ 500）是城市的个数，顺便假设城市的编号为 0~(n-1)；m 是高速公路的条数；s 是出发地的城市编号；d 是目的地的城市编号。随后的 m 行中，每行给出一条高速公路的信息，分别是：城市 1、城市 2、高速公路长度、收费额，中间用空格分开，数字均为整数且不超过 500。输入保证解的存在。
输出
在一行里输出路径的长度和收费总额，数字间以空格分隔，输出结尾不能有多余空格。
样例输入
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

首先，我们需要定义一些数据结构来存储城市、高速公路和距离、收费等信息。可以使用结构体来定义城市和高速公路，使用二维数组来存储城市之间的距离和收费。

接下来，我们可以使用Dijkstra算法来寻找最短路径。算法的核心是不断更新dist和charge数组，直到终点被访问。具体实现时，我们可以先初始化dist和charge数组，然后将起点标记为已访问，并更新其邻居节点的距离和收费。然后，从未访问的节点中选择一个距离起点最短的节点，将其标记为已访问，并更新其邻居节点的距离和收费。重复这个过程，直到终点被访问。

最后，输出终点所在节点的dist值和charge值即可。这个算法的时间复杂度是O(n^2)，其中n是城市的数量。由于题目给出的时间限制是1000ms，这个算法可以在规定时间内完成计算。

以下是具体的C语言代码实现：

#include <stdio.h>
#include <limits.h>

#define INF 99999  // 定义无穷大值

int main() {
    int n, m, s, d;  // 城市数量、高速公路数量、起点、终点
    scanf("%d %d %d %d", &n, &m, &s, &d);
    int graph[n][n] = {INF};  // 初始化高速公路信息
    int charge[n][n] = {INF};  // 初始化收费信息
    int dist[n];  // 记录从起点到每个节点的最短距离
    int pre[n];  // 记录最短路径上的前驱节点
    int visited[n] = {0};  // 记录节点是否被访问过
    int minDistance = INF;  // 记录当前最短距离
    int minNode = -1;  // 记录当前最短距离的节点编号
    int cost = 0;  // 记录当前总收费额
    for (int i = 0; i < m; i++) {  // 读入高速公路信息并存储到数组中
        int a, b, c, d;
        scanf("%d %d %d %d", &a, &b, &c, &d);
        graph[a][b] = c;  // 记录城市间的距离信息
        charge[a][b] = d;  // 记录城市间的收费信息（注意：对称矩阵）
    }
    for (int i = 0; i < n; i++) {  // 初始化dist和pre数组
        dist[i] = graph[s][i];  // 从起点到每个节点的距离初始化为起点到该节点的距离值（可能存在无法到达的情况）pre数组也一并初始化。pre[i]初始化为起点编号s。因为可能有多条最短路径，所以这里需要记录前驱节点以回溯路径。dist数组中的INF表示无法到达的节点，这里初始化为起点到该节点的距离值也是为了方便后面的比较操作。因为如果存在无法到达的节点，那么该节点的最短距离应该是无穷大（INF），而不是未定义的值（例如未初始化的值）。因此，这里初始化为起点到该节点的距离值可以保证后续的比较操作能够正确进行。因为如果存在多条最短路径长度相等的情况，我们需要选择其中一条最便宜的路径输出。所以我们需要记录每个节点的最短路径的前驱节点，以便回溯路径并输出最便宜的路径。初始化时将所有节点的最短路径长度都设为无穷大（INF），表示初始状态下没有任何路径可达这些节点。同时，初始化pre数组为起点编号s，表示初始状态下所有节点的最短路径都经过起点s。在后续的算法运行过程中，我们将不断更新这些值以找到最短路径和最便宜的路径。在初始化过程中需要注意的一点是：如果存在无法到达的节点（即INF值），我们不能将其设为未定义的值（例如垃圾值）。否则在后继比较操作中可能会导致错误的比较结果或者无法正确更新最短距离和收费额等变量值的问题。，因为后面的比较操作会依赖于这些初始值。，我们需要将所有节点的状态都初始化为可比较的状态（即不是未定义的值），以确保算法的准确性和稳定性。所以这里的初始化操作是非常重要的。然后设置起点为已访问状态visited[s]=1;，并设置dist[s]=0;，表示从起点出发的距离为0；将其他所有节点设为未访问状态visited[i]=0;，并将它们的dist值初始化为无穷大（INF