【问题描述】 给出一个有向图G=(V E)，和一个源点v0∈V，请写一个程序输出v0和图G中其它顶点的 最短路径。只要所有的有向环权值和都是正的，我们就允许图的边有负值。顶点的标号从 1 到n（n为图G的顶点数）。 【输入格式】 第 1 行：一个正数 n（2<=n<=80），表示图 G 的顶点总数。 第 2 行：一个整数，表示源点v0（v0∈V，v0可以是图G中任意一个顶点）。 第 3 至第 n+2 行，用一个邻接矩阵 W 给出了这个图。 【输出格式】 共包含 n-1 行，按照顶点编号从小到大的顺序，每行输出源点 v0 到一个顶点的最短距离。每行的具体格式参照样例。 【样例输入】 5 1 0 2 - - 10 - 0 3 - 7 - - 0 4 - - - - 0 5 - - 6 - 0 【样例输出】 (1 -> 2) = 2 (1 -> 3) = 5 (1 -> 4) = 9 (1 -> 5) = 9 用C语言写

以下是一个C语言的实现，使用了Dijkstra算法来求解最短路径：

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

#define INF 0x3f3f3f3f
#define MAXN 85

int n, s;
int w[MAXN][MAXN];
int dis[MAXN];
int vis[MAXN];

void dijkstra(int s) {
    memset(vis, 0, sizeof(vis));
    memset(dis, INF, sizeof(dis));
    dis[s] = 0;
    for (int i = 1; i < n; i++) {
        int u = -1;
        for (int j = 1; j <= n; j++) {
            if (!vis[j] && (u == -1 || dis[u] > dis[j])) {
                u = j;
            }
        }
        vis[u] = 1;
        for (int j = 1; j <= n; j++) {
            if (!vis[j] && w[u][j] != -1) {
                if (dis[j] > dis[u] + w[u][j]) {
                    dis[j] = dis[u] + w[u][j];
                }
            }
        }
    }
}

int main() {
    scanf("%d%d", &n, &s);
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= n; j++) {
            scanf("%d", &w[i][j]);
        }
    }
    dijkstra(s);
    for (int i = 1; i <= n; i++) {
        if (i != s) {
            printf("(%d -> %d) = %d\n", s, i, dis[i] == INF ? -1 : dis[i]);
        }
    }
    return 0;
}

输入格式：
第一行是一个正整数n，表示图G的顶点总数。
第二行是一个整数，表示源点v0。
接下来n行是一个邻接矩阵W，表示这个图。

输出格式：
共包含n-1行，按照顶点编号从小到大的顺序，每行输出源点v0到一个顶点的最短距离。每行的具体格式参照样例。

输入样例：
5
1
0 2 - - 10
- 0 3 - 7
- - 0 4 -
- - - 0 5
6 - 0 - -

输出样例：
(1 -> 2) = 2
(1 -> 3) = 5
(1 -> 4) = 9
(1 -> 5) = 9