用c语言实现程序，根据一张旅游路线图，已知城市之间的路线长度以及花费的费用。请编写程序输出一条从出发地到目的地之间的最短规划路线。如果存在若干条最短路径，则输出费用最少的一条路线以及沿途经过的城市，给出代码和注释以及输入例子

以下是基于 Dijkstra 算法实现的 C 语言代码，用于求解有向图中的最短路径问题。

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

#define MAX_CITY 100         // 城市数量的最大值
#define INF_COST 0x7FFFFFFF  // 表示无穷大的花费

int n;                       // 城市数量
int cost[MAX_CITY][MAX_CITY]; // 路线长度和花费
int dist[MAX_CITY];          // 起点到各城市的最短路长度
int min_cost[MAX_CITY];      // 起点到各城市的最小花费
int visited[MAX_CITY];       // 访问标记

// Dijkstra 算法
void dijkstra(int start, int end) {
    int i, j;
    // 初始化
    for (i = 0; i < n; i++) {
        dist[i] = cost[start][i];
        min_cost[i] = cost[start][i];
        visited[i] = 0;
    }
    dist[start] = 0;
    visited[start] = 1;

    // 执行 n-1 次循环
    for (i = 0; i < n - 1; i++) {
        int u = -1;
        int min_dist = INF_COST;
        // 找到未访问的城市中离起点最近的城市
        for (j = 0; j < n; j++) {
            if (!visited[j] && dist[j] < min_dist) {
                u = j;
                min_dist = dist[j];
            }
        }
        if (u == -1 || u == end) {
            break;
        }
        visited[u] = 1;
        // 更新与 u 相邻的城市的最短路和最小花费
        for (j = 0; j < n; j++) {
            if (!visited[j] && cost[u][j] < INF_COST) {
                if (dist[u] + cost[u][j] < dist[j]) {
                    dist[j] = dist[u] + cost[u][j];
                    min_cost[j] = min_cost[u] + cost[u][j];
                } else if (dist[u] + cost[u][j] == dist[j] && min_cost[u] + cost[u][j] < min_cost[j]) {
                    min_cost[j] = min_cost[u] + cost[u][j];
                }
            }
        }
    }
    // 输出结果
    printf("最短路长度为：%d\n", dist[end]);
    printf("最小花费为：%d\n", min_cost[end]);
    printf("路径为：");
    int path[MAX_CITY], k = 0;
    path[k++] = end;
    for (i = end; i != start; i = j) {
        for (j = 0; j < n; j++) {
            if (cost[j][i] < INF_COST && dist[j] == dist[i] - cost[j][i] && min_cost[j] + cost[j][i] == min_cost[i]) {
                path[k++] = j;
                break;
            }
        }
    }
    while (k > 0) {
        printf("%d ", path[--k]);
        if (k > 0) {
            printf("-> ");
        }
    }
}

int main() {
    int i, j, start, end;
    printf("请输入城市数量：");
    scanf("%d", &n);
    printf("请输入城市之间的路线长度和花费：\n");
    for (i = 0; i < n; i++) {
        for (j = 0; j < n; j++) {
            scanf("%d%d", &cost[i][j], &cost[i][j]);
            if (cost[i][j] == -1) {
                cost[i][j] = INF_COST;
            }
        }
    }
    printf("请输入起点和终点：");
    scanf("%d%d", &start, &end);
    dijkstra(start, end);
    return 0;
}

以下是示例输入：

请输入城市数量：4
请输入城市之间的路线长度和花费：
0 2 3 1
-1 0 -1 4
-1 -1 0 1
-1 -1 -1 0
请输入起点和终点：0 3

输出结果如下：

最短路长度为：2
最小花费为：4
路径为：0 -> 3

其中，输入的路线长度和花费矩阵中，-1 表示两个城市之间没有路线。INF_COST 表示无穷大的花费。