用c语言实现单源最短路问题，某国有 n个城市和m条单向火车，可能存在重边和自环，所有火车费用均为正值。请你求出 1号城市到 n号城市的最少费用，如果无法从1号城市走到n号城市，则输出-1。 Input 第一行包含整数n和m。(1<=n<=500, 1<=m<100000) 接下来m行每行包含三个整数x,y,z，表示存在一条从城市 x到城市y的火车，价格为z。Output 输出一个整数，表示 1号城市到n号城市的最少费用。 如果路径不存在，则输出 − 1

以下是使用Dijkstra算法实现的c语言代码：

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

#define MAXN 505
#define INF 0x3f3f3f3f

int n, m, s, t;
int head[MAXN], vis[MAXN], dis[MAXN], cnt[MAXN];

struct edge {
    int to, next, w;
} e[200005];

void add_edge(int u, int v, int w) {
    e[++m].to = v;
    e[m].w = w;
    e[m].next = head[u];
    head[u] = m;
}

void dijkstra(int s) {
    for (int i = 1; i <= n; i++) {
        dis[i] = INF;
        cnt[i] = 0;
    }
    dis[s] = 0;
    cnt[s] = 1;
    for (int i = 1; i <= n; i++) {
        int u = 0, minn = INF;
        for (int j = 1; j <= n; j++) {
            if (!vis[j] && dis[j] < minn) {
                minn = dis[j];
                u = j;
            }
        }
        if (!u) break;
        vis[u] = 1;
        for (int j = head[u]; j; j = e[j].next) {
            int v = e[j].to;
            if (dis[v] > dis[u] + e[j].w) {
                dis[v] = dis[u] + e[j].w;
                cnt[v] = cnt[u] + 1;
                if (cnt[v] > n) {
                    printf("-1");
                    exit(0);
                }
            }
        }
    }
}

int main() {
    scanf("%d%d", &n, &m);
    for (int i = 1; i <= m; i++) {
        int u, v, w;
        scanf("%d%d%d", &u, &v, &w);
        add_edge(u, v, w);
    }
    s = 1, t = n;
    dijkstra(s);
    if (dis[t] == INF) printf("-1");
    else printf("%d", dis[t]);
    return 0;
}

该算法的时间复杂度为O(n^2)，其中n为城市的数量。