c++给定有向网的顶点数、弧数、弧的信息，输出由给定源点出发到各个顶点的最短路径长度。X组测试数据，对于每组测试数据， 第一行输入顶点数N（N<=100），弧数M，给定源点，数据之间空格分隔； 第二行输入M条弧的信息（v1 v2 dut表示弧尾、弧头及权值），数据之间由空格分隔。按格式输出由给定源点出发到各个顶点的最短路径的长度。

这是一个经典的单源最短路径问题，可以使用Dijkstra算法或者Bellman-Ford算法解决。下面是使用Dijkstra算法的C++代码实现：

#include <iostream>
#include <cstring>
#define INF 0x3f3f3f3f
using namespace std;

int n, m, s; //顶点数，弧数，源点
int dis[105]; //源点到各个顶点的最短路径长度
bool vis[105]; //标记顶点是否已被访问
int g[105][105]; //邻接矩阵存储图

void Dijkstra()
{
    memset(vis, false, sizeof(vis));
    memset(dis, INF, sizeof(dis));
    dis[s] = 0;
    for(int i = 1; i <= n; i++)
    {
        int u = -1, minn = INF;
        for(int j = 1; j <= n; j++)
        {
            if(!vis[j] && dis[j] < minn)
            {
                u = j;
                minn = dis[j];
            }
        }
        if(u == -1) return; //图不连通
        vis[u] = true;
        for(int v = 1; v <= n; v++)
        {
            if(!vis[v] && g[u][v] != INF && dis[u] + g[u][v] < dis[v])
            {
                dis[v] = dis[u] + g[u][v];
            }
        }
    }
}

int main()
{
    while(cin >> n >> m >> s)
    {
        memset(g, INF, sizeof(g));
        for(int i = 1; i <= m; i++)
        {
            int u, v, w;
            cin >> u >> v >> w;
            g[u][v] = w;
        }
        Dijkstra();
        for(int i = 1; i <= n; i++)
        {
            if(dis[i] == INF) cout << "INF" << endl;
            else cout << dis[i] << endl;
        }
    }
    return 0;
}

输入格式：

5 7 1
1 2 2
1 3 3
2 4 1
2 5 4
3 4 2
4 5 3
5 3 5

输出格式：

0
2
3
5
8