# 计算机23级数据结构上级实验（第5-6周）

A 图的创建

分数 10

作者 朱允刚

单位 吉林大学

请编写程序创建一个有向图。有向图中包含n个顶点，编号为0至n-1。

输入格式:

输入第一行为两个正整数n和e，分别表示图的顶点数和边数，其中n不超过20000，e不超过20000。接下来e行表示每条边的信息，每行为3个非负整数a、b、c，其中a和b表示该边的端点编号，c表示权值。各边并非按端点编号顺序排列。

输出格式:

按顶点编号递增顺序输出每个顶点引出的边，每个顶点占一行，若某顶点没有引出边，则不输出。每行表示一个顶点引出的所有边，格式为a:(a,b,w)……，表示有向边a->b的权值为w，a引出的多条边按编号b的递增序排列。

输入样例:

7 7
0 1 5
0 3 7
0 6 6
1 2 4
2 5 1
3 5 3
6 5 4

输出样例:

0:(0,1,5)(0,3,7)(0,6,6)
1:(1,2,4)
2:(2,5,1)
3:(3,5,3)
6:(6,5,4)

解题思路：

1. 图的创建（CreateGraph）：我们读取节点数 n 和边数 e，然后根据输入的每条边的起点、终点和权重信息调用 addedge 函数来构建图。
2. 排序邻接表：在每次添加边时，我们不立即排序，而是通过调用 std::sort 排序每个节点的邻接边，使其按目标节点编号递增。
   • 关键在于目标节点编号递增；
3. 输出图的邻接表：通过遍历邻接表，打印每个节点的出边信息，格式符合题目要求。

#include<iostream>
#include<vector>

using namespace std;

// 边类定义，包含两个成员变量：目标节点v和权重w
class edge
{
public:
    int v;  // 目标节点
    int w;  // 边的权重

    // 构造函数，初始化目标节点和边的权重
    edge(int _v, int _w) :v(_v), w(_w){ }
};

// 存储图的邻接表，vextices[i]表示节点i的所有边
vector<vector<edge>> vextices;

// 比较函数，用于按边的权重排序
bool cmp(edge a, edge b)
{
    return a.w < b.w;  // 比较边的权重，升序排列
}

// 向图中添加一条边，并按权重排序
void addedge(int u, int v, int w)
{
    edge p(v, w);  // 创建边对象
    vextices[u].push_back(p);  // 将边添加到节点u的邻接表
}

// 创建图，输入节点数量和边数量，并添加相应的边
void CreateGraph()
{
    int n, e;
    cin >> n >> e;  // 输入图的节点数n和边数e
    vextices.resize(n);  // 调整vextices大小，确保可以容纳n个节点

    // 输入每一条边的信息
    for (int i = 0; i < e; i++)
    {
        int u, v, w;
        cin >> u >> v >> w;  // 输入边的起点u、终点v和权重w
        addedge(u, v, w);  // 添加边到图中
    }

    for(int i=0;i<n;i++)
    {
         // 按权重对邻接表进行排序
         std::sort(vextices[i].begin(), vextices[u].end(), cmp);
    }
}

// 打印图的邻接表
void printGraph()
{
    // 遍历图的所有节点及其邻接边
    for (int i = 0; i < vextices.size(); i++)
    {
        // 如果节点i有邻接边，打印该节点的邻接表
        if (vextices[i].size() != 0)
        {
            cout << i << ":";  // 打印当前节点
            for (int j = 0; j < vextices[i].size(); j++)
            {
                // 打印每一条邻接边的信息，格式：(起点, 终点, 权重)
                cout << "(" << i << "," << vextices[i][j].v << "," << vextices[i][j].w << ")";
            }
            cout << endl;  // 换行
        }
    }
}

int main()
{
    CreateGraph();  // 创建图
    printGraph();   // 打印图的邻接表
}

B 图深度优先遍历

分数 10

作者 朱允刚

单位 吉林大学

编写程序对给定的有向图（不一定连通）进行深度优先遍历，图中包含n个顶点，编号为0至n-1。本题限定在深度优先遍历过程中，如果同时出现多个待访问的顶点，则优先选择编号最小的一个进行访问，以顶点0为遍历起点。

输入格式:

输入第一行为两个整数n和e，分别表示图的顶点数和边数，其中n不超过20000，e不超过50。接下来e行表示每条边的信息，每行为两个整数a、b，表示该边的端点编号，但各边并非按端点编号顺序排列。

输出格式:

输出为一行整数，每个整数后一个空格，即该有向图的深度优先遍历结点序列。

输入样例1:

3 3
0 1
1 2
0 2

输出样例1:

0 1 2

输入样例2:

4 4
0 2
0 1
1 2
3 0

输出样例2:

0 1 2 3

解题思路：

1. 图的创建：通过输入边的信息，调用 addedge 添加边到邻接表中。
2. 深度优先搜索：通过递归的方式遍历图的所有连通分量。
3. 排序邻接表：每次添加新边后，使用简单的冒泡排序按目标节点编号排序邻接边。

#include<iostream>
#include<vector>

using namespace std;

// 边类定义，包含目标节点v和边的权重w，权重默认为1
class edge
{
public:
    int v;  // 目标节点
    int w;  // 边的权重，默认值为1

    // 构造函数，初始化目标节点v和边的权重w
    edge(int _v, int _w = 1) : v(_v), w(_w) { }
};

// 存储图的邻接表，vextices[i]表示节点i的所有出边
vector<vector<edge>> vextices;

// 访问标记数组，用于记录每个节点是否被访问
vector<bool> vis;

// 向图中添加一条边(u, v)，并按照目标节点v进行排序
void addedge(int u, int v)
{
    edge p(v);  // 创建一个表示边的对象，默认权重为1

    vextices[u].push_back(p);  // 将边添加到节点u的邻接表

    // 对邻接表按照目标节点v进行排序
    // 用冒泡排序方法将当前添加的边按目标节点编号升序排列
    for (int i = vextices[u].size() - 1; i > 0 && vextices[u][i].v < vextices[u][i - 1].v; i--)
    {
        swap(vextices[u][i], vextices[u][i - 1]);  // 交换位置
    }
}

// 创建图，输入节点数量n和边数量e，并添加相应的边
void CreateGraph(int n, int e)
{
    vextices.resize(n);  // 调整vextices大小，确保可以容纳n个节点

    // 输入每一条边的信息，并添加到图中
    for (int i = 0; i < e; i++)
    {
        int u, v;
        cin >> u >> v;  // 输入边的起点u和终点v
        addedge(u, v);   // 添加边到图中
    }
}

// 深度优先搜索（DFS），从节点u开始遍历所有连通节点
void dfs(int u)
{
    vis[u] = true;  // 标记节点u为已访问
    cout << u << " ";  // 输出当前节点

    // 遍历当前节点u的所有邻接边
    for (int i = 0; i < vextices[u].size(); i++)
    {
        // 如果目标节点v没有被访问过，继续递归DFS
        if (!vis[vextices[u][i].v])
        {
            dfs(vextices[u][i].v);
        }
    }
}

// 执行图的深度优先搜索，遍历所有节点，确保每个连通分量都被遍历
void do_dfs(int n)
{
    vis.resize(n, false);  // 初始化访问标记数组，所有节点未访问

    // 遍历所有节点，确保每个连通分量都被访问
    for (int i = 0; i < n; i++)
    {
        if (!vis[i])  // 如果节点i未访问过，执行DFS
        {
            dfs(i);  // 从节点i开始深度优先搜索
        }
    }
}

int main()
{
    int n, e;
    cin >> n >> e;  // 输入图的节点数n和边数e

    CreateGraph(n, e);  // 创建图并添加边

    do_dfs(n);  // 从所有未访问的节点开始深度优先搜索并输出结果
}

C 任务排序

分数 10

作者 吉林大学

单位 吉林大学

一个工程被分解成n个子任务，编号为0至n-1。要完成整个工程需要完成所有的子任务。其中一些子任务必须先于另外一些子任务被完成。给定各子任务之间的先后关系，请编写程序给出一个合理的任务完成顺序，若工程不可行，程序亦能识别。

输入格式:

输入第一行为两个整数n和e，均不超过100。n表示子任务数。接下来e行，表示已知的两个子任务间的先后关系，每行为两个整数a和b，表示任务a必须先于任务b完成。

输出格式:

若工程不可行（一些子任务以自己为先决条件），输出“unworkable project”；若工程可行，输出为1行整数，每个整数后一个空格，为n个子任务的编号，表示子任务的完成顺序，如果有多种可能的顺序，则输出字典序最小者。

注：字典序，即对象在字典中的顺序。对于两个数字序列，从第一个数字开始比较，当某一个位置的数字不同时，该位置数字较小的序列，字典序较小，例如1 2 3 9比1 2 4 5小，1 2 8 9比1 2 10 3小。

输入样例1:

3 2
0 1
1 2

输出样例1:

0 1 2

输入样例2:

3 3
0 1
1 2
2 0

输出样例2:

unworkable project

解题思路：

• 建图同上题
• 拓扑排序：通过 Kahn 算法，使用入度数组和一个队列（zero_in_degree）来处理入度为零的节点，并按字典序进行排序。如果图中存在环，无法进行拓扑排序。
• 注意字典序

#include<iostream>
#include<vector>
#include<queue>

using namespace std;

// 边类，包含目标节点v和边的权重w，默认权重为1
class edge
{
public:
    int v;  // 目标节点
    int w;  // 边的权重，默认为1

    // 构造函数，初始化目标节点v和边的权重w
    edge(int _v, int _w = 1) : v(_v), w(_w) { }
};

// 图的邻接表表示，vextices[i]表示节点i的所有出边
vector<vector<edge>> vextices;

// 访问标记数组，用于记录每个节点是否被访问
vector<bool> vis;

// 向图中添加一条边(u, v)，并按照目标节点v对邻接表进行排序
void addedge(int u, int v)
{
    edge p(v);  // 创建一个表示边的对象，默认权重为1

    vextices[u].push_back(p);  // 将边添加到节点u的邻接表

    // 对邻接表按照目标节点v进行排序（升序排列）
    for (int i = vextices[u].size() - 1; i > 0 && vextices[u][i].v < vextices[u][i - 1].v; i--)
    {
        swap(vextices[u][i], vextices[u][i - 1]);  // 交换位置
    }
}

// 创建图，输入节点数量n和边数量e，并添加相应的边
void CreateGraph(int n, int e)
{
    vextices.resize(n);  // 调整vextices大小，确保可以容纳n个节点

    // 输入每一条边的信息，并添加到图中
    for (int i = 0; i < e; i++)
    {
        int u, v;
        cin >> u >> v;  // 输入边的起点u和终点v
        addedge(u, v);   // 添加边到图中
    }
}



// 拓扑排序函数，返回一个拓扑排序的结果
vector<int> TopologicalSort()
{
    int number = vextices.size();  // 获取图的节点数

    vector<int> Topo;  // 用于记录拓扑排序的结果
    vector<int> zero_in_degree;  // 用于记录入度为0的顶点
    vector<int> indegree(number, 0);  // 存储每个节点的入度，初始化为0

    // 计算每个节点的入度
    for (int u = 0; u < number; u++)
    {
        for (int v = 0; v < vextices[u].size(); v++)
        {
            indegree[vextices[u][v].v]++;  // 目标节点v的入度加1
        }
    }

    // 将所有入度为0的节点放入zero_in_degree中，并确保其升序排列
    for (int i = number - 1; i >= 0; i--)
    {
        if (indegree[i] == 0)
        {
            zero_in_degree.push_back(i);  // 入度为0的节点加入队列
        }
    }

    // Kahn算法进行拓扑排序
    while (!zero_in_degree.empty())
    {
        // 取出入度为0的节点处理
        int u = zero_in_degree.back();
        zero_in_degree.pop_back();

        // 将节点u加入拓扑排序结果
        Topo.push_back(u);

        // 更新邻接边的入度
        for (int i = 0; i < vextices[u].size(); i++)
        {
            indegree[vextices[u][i].v]--;  // 目标节点v的入度减1
            if (indegree[vextices[u][i].v] == 0)
            {
                // 如果目标节点v的入度变为0，将其加入zero_in_degree中
                zero_in_degree.push_back(vextices[u][i].v);

                // 保证zero_in_degree队列按节点编号升序排列
                for (int i = zero_in_degree.size() - 1; i > 0 && zero_in_degree[i] > zero_in_degree[i - 1]; i--)
                {
                    swap(zero_in_degree[i], zero_in_degree[i - 1]);  // 交换节点
                }
            }
        }
    }

    // 检查是否存在环，如果拓扑排序的结果节点数不等于图的节点数，则说明图中有环
    if (Topo.size() != number)
    {
        return {};  // 返回空数组表示图中有环
    }

    // 返回拓扑排序的结果
    return Topo;
}

int main()
{
    int n, e;
    cin >> n >> e;  // 输入图的节点数n和边数e

    CreateGraph(n, e);  // 创建图并添加边

    vector<int> topo = TopologicalSort();  // 获取拓扑排序结果

    // 如果拓扑排序结果为空，说明图中有环
    if (topo.empty())
    {
        cout << "unworkable project";  // 输出无法完成的项目
    }
    else
    {
        // 输出拓扑排序的结果
        for (const auto i : topo)
        {
            cout << i << " ";  // 输出排序后的节点
        }
    }
}

D 冬奥会接驳车

分数 10

作者 朱允刚

单位 吉林大学

2022年冬奥会科技感十足，奥组委配备了无人驾驶的接驳车。假定你是奥组委的软件工程师，请你为无人接驳车编写路径规划程序，使其载着运动员以最短的时间到达目的地。

接驳车的运行范围可以被建模为一张由n行m列单元格组成的地图。有的单元格是空地，可以走；有的单元格处是障碍物，不能走。假定接驳车只可以朝上、下、左、右四个方向行驶，不能斜着走。每行驶过一个位置（单元格）需要1分钟。给定地图以及运动员的起点和终点，请输出接驳车从起点行驶到终点所需的最短时间。

输入格式:

输入包含多组数据。每组数据第一行是两个整数n和m (1≤ m, n ≤100)，表示地图的长和宽；接下来是n行，每行m个数字，表示整个地图。空地格子用0表示，障碍物用1表示，运动员所在起点用3表示，目的地用4表示。

输出格式:

对于每组数据，如果接驳车能够到达目的地，输出一个整数，表示运动员从起点到目的地所需的最短时间，如果不能到达目的地，输出“unreachable”。

输入样例:

5 5
1 0 1 1 1
1 0 4 1 0
1 0 0 1 0
0 0 0 1 0
1 0 3 0 1
5 5
3 0 1 1 1
1 0 1 1 0
1 0 1 1 0
0 0 0 1 0
1 0 1 0 4

输出样例:

3
unreachable

解题思路

关键点在于直接利用所给的二维数组建立图

1. 初始化图：
   • 通过输入生成图，并标记起点startpoint和终点endpoint的位置。为了方便处理边界，可以将图的大小扩展为(n+2) * (m+2)，避免边界判断。扩展后的矩阵外层填充1，表示墙壁，确保不越界。
   • 并记录起始点
2. BFS广度优先搜索：
   • 由于我们需要找的是从起点到终点的最短路径，且每个节点的权重相同（不考虑权重），广度优先搜索（BFS）是一个很合适的选择。
   • BFS的特点是按层次进行遍历，保证了每次访问的节点都是离起点最近的。
3. BFS的操作：
   • 使用队列来进行广度优先遍历，队列中保存当前的节点坐标。
   • 每次从队列中取出一个节点，遍历该节点的四个邻居（上下左右），如果邻居是一个可行走的节点（即graph[i][j] != 1）并且还没有访问过，就将其加入队列，更新其到起点的距离。
   • 继续进行直到队列为空或终点被找到。
4. 检查结果：
   • 如果终点的距离不是INT_MAX，表示可以到达，输出距离；否则，输出unreachable。

#include<iostream>
#include<vector>
#include<queue>
#include<climits>  // 用于处理INT_MAX，表示无穷大

using namespace std;

// 图的邻接矩阵表示
vector<vector<int>> graph;

// 起始点和终点的位置
pair<int, int> startpoint;
pair<int, int> endpoint;

// 创建图，并初始化起始点和终点
void CreateGraph(int n, int m)
{
    graph.clear();  // 清空图数据

    // 增大矩阵的大小以避免边界处理，确保图内元素能够存储在一个大小为(n+2)*(m+2)的矩阵中
    graph.resize(n + 2, vector<int>(m + 2, 1));  // 将矩阵初始化为1，1表示不可行走的地方

    // 输入图的数据并定位起始点和终点
    for (int i = 1; i <= n; i++)
    {
        for (int j = 1; j <= m; j++)
        {
            int v;
            cin >> v;  // 读取每个位置的值

            // 记录起始点和终点的位置
            if (v == 3)  // 起始点
            {
                startpoint = make_pair(i, j);
            }
            if (v == 4)  // 终点
            {
                endpoint = make_pair(i, j);
            }

            graph[i][j] = v;  // 将输入的值存入图
        }
    }
}

// 处理从点u到点v的移动，并更新dist矩阵
void addresspoint(pair<int, int> u, pair<int, int> v, vector<vector<int>>& dist, queue<pair<int, int>>& q)
{
    // 如果u等于v，说明已经到达目标点，直接返回
    if (u == v) return;

    // 如果v的值是1，表示不可行走的地方，直接返回
    if (graph[v.first][v.second] == 1) return;

    // 如果v尚未访问过（dist[v.first][v.second] == INT_MAX），将其加入队列，并更新距离
    if (dist[v.first][v.second] == INT_MAX)
    {
        q.push(v);  // 将v加入队列，准备处理
        dist[v.first][v.second] = dist[u.first][u.second] + 1;  // 更新v的最短距离
    }
}

// 进行广度优先搜索（BFS）来计算从起始点到所有节点的最短路径
void ShortPath(pair<int, int> u, vector<vector<int>>& dist)
{
    // 如果起始点已经访问过，直接返回
    if (dist[u.first][u.second] != INT_MAX) return;

    dist[u.first][u.second] = 0;  // 起始点的距离为0

    // 创建一个队列用于BFS
    queue<pair<int, int>> q;
    q.push(u);  // 将起始点加入队列

    // 广度优先搜索
    while (!q.empty())
    {
        pair<int, int> v = q.front();  // 取队列头部元素
        q.pop();  // 弹出队列头部元素

        // 遍历v的四个方向（上下左右），并更新它们的距离
        addresspoint(v, make_pair(v.first + 1, v.second), dist, q);  // 下
        addresspoint(v, make_pair(v.first - 1, v.second), dist, q);  // 上
        addresspoint(v, make_pair(v.first, v.second + 1), dist, q);  // 右
        addresspoint(v, make_pair(v.first, v.second - 1), dist, q);  // 左
    }
}

// 计算起始点到终点的最短路径，并输出结果
void do_ShortPath(int n, int m)
{
    // 初始化距离矩阵，所有值初始化为INT_MAX，表示不可达
    vector<vector<int>> dist(n + 2, vector<int>(m + 2, INT_MAX));

    // 从起始点开始进行广度优先搜索，更新距离矩阵
    ShortPath(startpoint, dist);

    // 如果终点的距离不为INT_MAX，表示可达，输出最短路径距离
    if (dist[endpoint.first][endpoint.second] != INT_MAX)
    {
        cout << dist[endpoint.first][endpoint.second] << endl;
    }
    else
    {
        // 如果终点的距离仍为INT_MAX，表示不可达，输出“unreachable”
        cout << "unreachable" << endl;
    }
}

int main()
{
    int n, m;
    while (cin >> n >> m)  // 持续输入图的大小和数据
    {
        CreateGraph(n, m);  // 创建图
        do_ShortPath(n, m);  // 计算并输出从起点到终点的最短路径
    }
}

E 单源最短路径

分数 10

作者 朱允刚

单位 吉林大学

请编写程序求给定正权有向图的单源最短路径长度。图中包含n个顶点，编号为0至n-1，以顶点0作为源点。

输入格式:

输入第一行为两个正整数n和e，分别表示图的顶点数和边数，其中n不超过20000，e不超过1000。接下来e行表示每条边的信息，每行为3个非负整数a、b、c，其中a和b表示该边的端点编号，c表示权值。各边并非按端点编号顺序排列。

输出格式:

输出为一行整数，为按顶点编号顺序排列的源点0到各顶点的最短路径长度（不含源点到源点），每个整数后一个空格。如源点到某顶点无最短路径，则不输出该条路径长度。

输入样例:

4 4
0 1 1
0 3 1
1 3 1
2 0 1

输出样例:

1 1

解题思路

• 重点在于使用优先队列优化算法

// 使用优先队列实现Dijkstra算法计算最短路径以优化时间
void queue_ShortPath(int start, vector<int>& dist)
{
    dist[start] = 0;  // 起点的距离设为0

    // 优先队列，存储 (距离, 节点) 对，按距离升序排列
    priority_queue < pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>>> pq;
    pq.push({ 0, start });  // 将起点加入队列

    // 队列非空时继续处理
    while (!pq.empty())
    {
        int d = pq.top().first;  // 当前节点的距离
        int u = pq.top().second; // 当前节点
        pq.pop();

        // 如果当前距离大于已知最短距离，跳过，即已经更新的点
        if (d > dist[u]) continue;

        // 遍历当前节点u的所有出边
        for (const auto& e : vertices[u])
        {
            int v = e.v;  // 目标节点
            int w = e.w;  // 边的权重

            // 如果从u到v的距离更短，则更新v的最短距离
            if (dist[u] + w < dist[v])
            {
                dist[v] = dist[u] + w;  // 更新v的最短路径
                pq.push({ dist[v], v });  // 将更新后的节点加入队列
            }
        }
    }
}

#include<iostream>
#include<vector>
#include<queue>
#include<climits>
using namespace std;

// 边类定义，包含目标节点v和权重w
class edge
{
public:
    int v;  // 目标节点
    int w;  // 边的权重

    // 构造函数初始化目标节点v和权重w
    edge(int _v, int _w = 1) : v(_v), w(_w) { }
};

vector<vector<edge>> vertices;  // 图的邻接表，保存每个节点的出边
vector<bool> vis;  // 记录节点是否已经访问

// 向图中添加一条边
void addedge(int u, int v, int w)
{
    // 创建一条从u到v的边，权重为w
    edge p(v, w);
    vertices[u].push_back(p);
}

// 创建图，输入节点数量n和边的数量e，建立邻接表
void CreateGraph(int n, int e)
{
    vertices.resize(n);  // 根据节点数调整邻接表的大小

    // 输入每条边的信息，建立图的边
    for (int i = 0; i < e; i++)
    {
        int u, v, w;
        cin >> u >> v >> w;  // 输入边的起点u，终点v和权重w
        addedge(u, v, w);     // 将边添加到图中
    }
}

// 使用优先队列实现Dijkstra算法计算最短路径以优化时间
void queue_ShortPath(int start, vector<int>& dist)
{
    dist[start] = 0;  // 起点的距离设为0

    // 优先队列，存储 (距离, 节点) 对，按距离升序排列
    priority_queue < pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>>> pq;
    pq.push({ 0, start });  // 将起点加入队列

    // 队列非空时继续处理
    while (!pq.empty())
    {
        int d = pq.top().first;  // 当前节点的距离
        int u = pq.top().second; // 当前节点
        pq.pop();

        // 如果当前距离大于已知最短距离，跳过，即已经更新的点
        if (d > dist[u]) continue;

        // 遍历当前节点u的所有出边
        for (const auto& e : vertices[u])
        {
            int v = e.v;  // 目标节点
            int w = e.w;  // 边的权重

            // 如果从u到v的距离更短，则更新v的最短距离
            if (dist[u] + w < dist[v])
            {
                dist[v] = dist[u] + w;  // 更新v的最短路径
                pq.push({ dist[v], v });  // 将更新后的节点加入队列
            }
        }
    }
}

// 经典的Dijkstra算法实现（没有使用优先队列）
void ShortPath(int u, vector<int>& dist, vector<bool>& vis)
{
    vis[u] = true;  // 标记起点已访问
    dist[u] = 0;  // 起点到自身的距离为0

    // 初始化dist数组，起点的邻接边的距离
    for (int i = 0; i < vertices[u].size(); i++)
    {
        dist[vertices[u][i].v] = vertices[u][i].w;
    }

    // 遍历所有节点，更新最短路径
    for (int i = 1; i < dist.size(); i++)
    {
        int min = INT_MAX;
        int v = u;

        // 找到当前未访问的节点中距离最小的节点
        for (int j = 0; j < dist.size(); j++)
        {
            if (!vis[j] && dist[j] < min)
            {
                v = j;
                min = dist[j];
            }
        }

        // 标记当前节点已访问
        vis[v] = true;

        // 更新v的邻接边
        for (int k = 0; k < vertices[v].size(); k++)
        {
            if (!vis[vertices[v][k].v] && dist[v] + vertices[v][k].w < dist[vertices[v][k].v])
            {
                dist[vertices[v][k].v] = dist[v] + vertices[v][k].w;  // 更新最短路径
            }
        }
    }
}

// 计算并输出从起点到所有其他节点的最短路径
void do_ShortPath(int n)
{
    vector<int> dist(n, INT_MAX);  // 初始化dist数组，默认每个节点的距离为无穷大

    if (n <= 0) return;

    // 使用优先队列实现Dijkstra算法，从起点0开始计算最短路径
    queue_ShortPath(0, dist);

    // 输出从起点到其他节点的最短路径
    for (int i = 1; i < n; i++)
    {
        if (dist[i] != INT_MAX)
        {
            cout << dist[i] << " ";  // 输出节点i的最短路径
        }
    }
}

int main()
{
    int n, e;
    cin >> n >> e;  // 输入节点数和边数

    CreateGraph(n, e);  // 创建图

    do_ShortPath(n);  // 计算并输出最短路径
}