最小生成树,最短路径题组

  • Post author:
  • Post category:其他


目录:

1.洛谷P3366 【模板】最小生成树

2.洛谷P1991 无线通讯网

3.洛谷P2121 拆地毯

4.洛谷P2872[USACO07DEC]Building Roads S

5.洛谷P3371 【模板】单源最短路径(弱化版)

6.洛谷P1629 邮递员送信

7. 洛谷P1359 租用游艇

8.洛谷P4779 【模板】单源最短路径(标准版)

1.洛谷P3366 【模板】最小生成树

给出一个无向图,求出最小生成树,

该图连通,则输出一个整数表示最小生成树的各边的长度之和。

如果该图不连通则输出 orz如果该图不连通,则输出 orz

输入:

第一行包含两个整数N,M表示N个结点,M个无向边

思路:Kruskal 算法求最小生成树

#include<iostream>
#include<algorithm>
using namespace std;
const int maxn = 2e5 + 10;
int n, m,sum;
int fa[maxn];
struct node {
    int x, y, z;
}edge[maxn];
bool cmp(node a, node b) {
    return a.z < b.z;
}
int my_sort(int l, int r)  //快排
{
    if (l >= r)
        return 0;
    int i = l, j = r;
    node t, t1 = edge[l];
    while (i < j)
    {
        while (i < j && edge[j].z >= t1.z)
            j--;
        while (i < j && edge[i].z <= t1.z)
            i++;
        if (i < j) {
            t = edge[i];
            edge[i] = edge[j];
            edge[j] = t;
        }
    }
    edge[l] = edge[i];
    edge[i] = t1;
    my_sort(l, i - 1);
    my_sort(i + 1, r);
}
int find(int x) {  //找父结点
    return fa[x] == x ? x : fa[x] = find(fa[x]);
}
int main()
{
    ios::sync_with_stdio(false);
    cin >> n >> m;
    for (int i = 1; i <= m; i++) {
        cin >> edge[i].x >> edge[i].y >> edge[i].z;
    }
    for (int i = 1; i <= n; i++) {
        fa[i] = i;
    }
    /*sort(edge + 1, edge + 1 + m, cmp);*/
    my_sort(1,m);
    for (int i = 1; i <= m; i++) {    //每次添加最短的一条边
        int x = find(edge[i].x);
        int y = find(edge[i].y);
        if (x == y)continue;
        fa[min(x, y)] = max(x, y);
        sum += edge[i].z;
    }
    int ans = 0;
    for (int i = 1; i <= n; i++) {
        if (fa[i] == i)ans++;           //联通情况为所有结点父结点为同一个
    }
    if (ans > 1)cout << "orz" << '\n';   
    else cout << sum << '\n';
    return 0;
}


2.洛谷P1991 无线通讯网

输入

输入数据第 1 行,2 个整数 S,P;S表示可安装的卫星电话的哨所数,P表示边防哨所的数量

接下来P行表示坐标,每个边防哨所都要配备无线电收发器;有一些哨所还可以增配卫星电话。

无线电收发器通话的哨所之间的距离不能超过 D,

任意两个配备了一条卫星电话线路的哨所(两边都ᤕ有卫星电话)均可以通话,无论他们相距多远

输出

最小D,精确到小数点后两位。

思路:

Kruskal 算法求一个平面直角坐标系中的最小生成树中满足退出条件为p – s的最小边

Kruskal算法是通过并查集,按照边的权重顺序(从小到大)将边加入生成树中,

但是若加入该边会与生成树形成环则不加入该边,选其次。直到树中含有n – 1条边为止。

这道题退出条件变成了p – s

s一定留给最远的

#include<iostream>
#include<math.h> //sqrt头文件
using namespace std;
const int maxn = 2e5 + 10;
int s, p;
int fa[maxn];
double sum=0;
struct node {         //记录每座城市相连序号与距离
    int x, y;
    double s;
}edge[maxn];
struct recc {     //记录坐标
    double xx, yy;
}b[maxn];
int find(int x) { //查询父结点
    return fa[x] == x ? x : fa[x] = find(fa[x]);
}
int my_sort(int l, int r)  //快排
{
    if (l >= r)
        return 0;
    int i = l, j = r;
    node t, t1 = edge[l];
    while (i < j)
    {
        while (i < j && edge[j].s >= t1.s)
            j--;
        while (i < j && edge[i].s <= t1.s)
            i++;
        if (i < j) {
            t = edge[i];
            edge[i] = edge[j];
            edge[j] = t;
        }
    }
    edge[l] = edge[i];
    edge[i] = t1;
    my_sort(l, i - 1);
    my_sort(i + 1, r);
}
int main()
{
    ios::sync_with_stdio(false);
    cin >> s >> p;
    int flag = 0;
    for (int i = 1; i <= p; i++) {
        fa[i] = i;
        cin >> b[i].xx >> b[i].yy;
        for (int j = 1; j < i; j++) {
            edge[++flag].x = i;
            edge[flag].y = j;
            edge[flag].s= sqrt((b[i].xx - b[j].xx) * (b[i].xx - b[j].xx) + (b[i].yy - b[j].yy) * (b[i].yy - b[j].yy));//勾股定理
        }
    }
    my_sort(1, flag);
    int flag1 = 0;
    for (int i = 1; i <= flag; i++) { 每次添加最短的一条边
        int x = find(edge[i].x);
        int y = find(edge[i].y);
        if (x != y) {
            fa[min(x, y)] = max(x, y);
            flag1++;
            if (flag1 >= p - s) {
                printf("%.2f", edge[i].s);
                return 0;
            }
        }
    }
    return 0;
}


3.洛谷P2121 拆地毯

会场上有 n 个关键区域,不同的关键区域由 m 条无向地毯彼此连接。

每条地毯可由三个整数 u、v、w 表示,

其中 u 和 v 为地毯连接的两个关键区域编号,w 为这条地毯的美丽度。

组织者被要求只能保留 K 条地毯,

组织者要求新图中不能有环,算出这 K 条地毯的美丽度之和最大为多少。

输入格式

第一行包含三个正整数 n、m、K。

接下来 m 行中每行包含三个正整数 u、v、w。

输出格式

只包含一个正整数,表示这 K 条地毯的美丽度之和的最大值。

思路:

Kruskal算法是通过并查集,按照边的权重顺序(从小到大)将边加入生成树中,

但是若加入该边会与生成树形成环则不加入该边,选其次。直到树中含有n – 1条边为止。

这道题自需按从大到小排序,求最大生成树,退出条件为k

#include<iostream>
using namespace std;
const int maxn = 2e5 + 10;
int n, w, k;
int fa[maxn];
struct node {
    int x, y, z;
}edge[maxn];
int find(int x) {       //查询父结点
    return fa[x] == x ? x : fa[x] = find(fa[x]);
}
int my_sort(int l, int r)  //快排
{
    if (l >= r)
        return 0;
    int i = l, j = r;
    node t, t1 = edge[l];
    while (i < j)
    {
        while (i < j && edge[j].z <= t1.z)
            j--;
        while (i < j && edge[i].z >= t1.z)
            i++;
        if (i < j) {
            t = edge[i];
            edge[i] = edge[j];
            edge[j] = t;
        }
    }
    edge[l] = edge[i];
    edge[i] = t1;
    my_sort(l, i - 1);
    my_sort(i + 1, r);
}
int main()
{
    ios::sync_with_stdio(false);
    cin >> n >> w >> k;
    for (int i = 1; i <= n; i++) {
        fa[i] = i;
    }
    for (int i = 1; i <= w; i++) {
        cin >> edge[i].x >> edge[i].y >> edge[i].z;
    }
    my_sort(1, w);  //从大到小排序
    int sum = 0, flag = 0;
    for (int i = 1; i <= w; i++) { 每次添加最长的一条边
        int x = find(edge[i].x);
        int y = find(edge[i].y);
        if (x != y) {
            fa[min(x, y)] = max(x, y);
            sum += edge[i].z;
            flag++;
            if (flag == k)
                break;
        }
    }
    cout << sum << '\n';
    return 0;
}


4.洛谷P2872[USACO07DEC]Building Roads S

给定 n 个点的坐标,第 i 个点的坐标为(xi​, yi​),

这 n 个点编号为 1 到 n。给定 m 条边,第 i 条边连接第 ui​ 个点和第 vi​ 个点。

现在要求你添加一些边,并且能使得任意一点都可以连通其他所有点。

求添加的边的总长度的最小值。

输入:

第一行两个整数 n, m 代表点数与边数。

接下来 n 行每行两个整数 xi​, yi​ 代表第 i 个点的坐标。

接下来 m 行每行两个整数 ui​, vi​ 代表第 i 条边连接第 ui​ 个点和第 vi​ 个点。

输出:

一行一个实数代表添加的边的最小长度,要求保留两位小数,为了避免误差, 请用 64 位实型变量进行计算。

思路:

Kruskal算法求最小生成树,只需将一开始就存在的边权值赋为0即可

#include<iostream>
#include<math.h>//sqrt头文件
using namespace std;
const int maxn = 2e6 + 10;      //需开大点,防止RE
int n, m;
int fa[maxn];
double sum = 0.0;
struct node {//记录相连点序号和距离
    int x, y;
    double z;
}edge[maxn];
struct recc {//记录坐标
    double xx, yy;
}b[maxn];
int find(int x) {       //查询父结点
    return fa[x] == x ? x : fa[x] = find(fa[x]);
}
int my_sort(int l, int r)  //快排
{
    if (l >= r)
        return 0;
    int i = l, j = r;
    node t, t1 = edge[l];
    while (i < j)
    {
        while (i < j && edge[j].z >= t1.z)
            j--;
        while (i < j && edge[i].z <= t1.z)
            i++;
        if (i < j) {
            t = edge[i];
            edge[i] = edge[j];
            edge[j] = t;
        }
    }
    edge[l] = edge[i];
    edge[i] = t1;
    my_sort(l, i - 1);
    my_sort(i + 1, r);
}
int main()
{
    ios::sync_with_stdio(false);
    cin >> n >> m;
    int flag = 0;
    for (int i = 1; i <= n; i++) {
        fa[i] = i;
        cin >> b[i].xx >> b[i].yy;
        for (int j = 1; j < i; j++) {
            edge[++flag].x = i;
            edge[flag].y = j;
            edge[flag].z= ((b[i].xx - b[j].xx) * (b[i].xx - b[j].xx) + (b[i].yy - b[j].yy) * (b[i].yy - b[j].yy));//勾股定理
        }
    }
    for (int i = 1; i <= m; i++) {  //一开始存在的边赋为0
        int x, y;         //不需要更改原有边,添加即可
        cin >> x >> y;    //因为排序后在最前添加,添加后父结点一致,原有边不会进来
        edge[++flag].x = x;
        edge[flag].y = y;
        edge[flag].z = 0.0;
    }
    my_sort(1, flag);
    for (int i = 1; i <= flag; i++) { //每次添加最短的一条边
        int x = find(edge[i].x);
        int y = find(edge[i].y);
        if (x != y) {
            fa[min(x, y)] = max(x, y);
            sum += sqrt(edge[i].z);  //在加和的时候sqrt节省时间
        }
    }
    printf("%.2f", sum);
    return 0;
}


5.洛谷P3371 【模板】单源最短路径(弱化版)

如题,给出一个有向图,请输出从某一点出发到所有点的最短路径长度。

输入格式

第一行包含三个整数 n, m, s,分别表示点的个数、有向边的个数、出发点的编号。

接下来 m 行每行包含三个整数 u, v, w,表示一条 u -> v 的,长度为 w 的边。

输出格式

输出一行 n 个整数,第 i 个表示 s 到第 i 个点的最短路径,若不能到达则输出 2^31 – 1。

思路:

Dijkstra算法

Dijkstra是基于一种贪心的策略,用数组dis记录起点到每个结点的最短路径,

bool 数组vis表示是否来过,dis[s]=0,其余为2的31次方-1,

定义pos变量代表现在的位置,vis[pos]=true表示来过,初始值为起点

枚举所有与pos相连的点:更新dis[i]按照:dis[i]=min(dis[i],dis[pos]+w)

枚举所有未被标记的点,找到dis最小的点赋值给pos,vis[pos]==true;

所有点都访问过程序结束。此时,dis[i]代表从起点到i的最短路径

#include<iostream>
#include<cstring>//memset头文件
using namespace std;
typedef long long ll;
const int maxn = 1e6 + 10;
int head[maxn], cnt;
ll dis[maxn];
bool vis[maxn];
int m, n, s;
struct edge1{
    int u,w;
    int next;
    edge1(){}
    edge1(int _u, int _w, int _next) {     //简化插入操作
        u = _u;
        w = _w;
        next = _next;
    }
}edge[maxn];                         //链式前向星
void insert(int u, int v, int w){//头插法
    edge[++cnt]= edge1(v,w,head[u]);// 每一个新节点的next始终指向头结点的next;
    head[u] = cnt;//头结点的next始终指向新结点
}
void dijkstra(int s) {     //dijkstra算法
    dis[s] = 0;
    int pos = s;
    while (!vis[pos]){
        ll MIN = 2147483647;
        vis[pos] = true;
        for (int i = head[pos]; ~i; i = edge[i].next){ //~i==i!=-1
            if (!vis[edge[i].u] && dis[edge[i].u] > dis[pos] + edge[i].w){
                dis[edge[i].u] = dis[pos] + edge[i].w;
            }
        }
        for (int i = 1; i <= m; i++){
            if (dis[i] < MIN && vis[i] == 0){
                MIN = dis[i];
                pos = i;
            }
        }
    }
}
int main()
{
    ios::sync_with_stdio(false);
    cin >> m >> n >> s;
    for (int i = 1; i <= n; i++) {
        dis[i] = 2147483647; //2的31次方-1; 
    }
    memset(head, -1, sizeof(head));
    for (int i = 1; i <= n; i++) {  //插入边
        int u, v, w;
        cin >> u >> v >> w;
        insert(u, v, w);
    }
    dijkstra(s);
    for (int i = 1; i <= m; i++){   //s到1...n的最短路径
        cout << dis[i] << ' ';
    }
}


6.洛谷P1629 邮递员送信

有一个邮递员要送东西,邮局在节点 1。他总共要送 n – 1样东西,

其目的地分别是节点 2到节点 n。

由于这个城市的交通比较繁忙,因此所有的道路都是单行的,共有 m条道路。

这个邮递员每次只能带一样东西,并且运送每件物品过后必须返回邮局。

求送完这 n – 1 样东西并且最终回到邮局最少需要的时间。

输入格式

第一行包括两个整数,n 和 m,表示城市的节点数量和道路数量。

第二行到第(m + 1)行,每行三个整数,u, v, w,表示从 u 到 v 有一条通过时间为 w 的道路。

输出格式

输出仅一行,包含一个整数,为最少需要的时间。

思路:

因为是有向的,所以去的时候的路线和回来时候的路线不一定是一样的。

去的时候为一对多,回来多对一,所以回来时反向建图

反图可以把所有结点的编号+ m建在原图的体系中。

需要在dijkstra函数中加入判断以区分vis,当从起点和当从终点

#include<iostream>
#include<cstring>//memset头文件
using namespace std;
typedef long long ll;
const int maxn = 1e6 + 10;
int head[maxn], cnt;
ll dis[maxn],sum;
bool vis[maxn];
int m, n;
struct edge1 {
    int u, w;
    int next;
    edge1() {}
    edge1(int _u, int _w, int _next) {     //简化插入操作
        u = _u;
        w = _w;
        next = _next;
    }
}edge[maxn];                         //链式前向星
void insert(int u, int v, int w) {//头插法
    edge[++cnt] = edge1(v, w, head[u]);// 每一个新节点的next始终指向头结点的next;
    head[u] = cnt;//头结点的next始终指向新结点
}
void dijkstra(int s) {     //dijkstra算法
    for (int i = 1; i <= m<<1; i++) {
        dis[i] = 2147483647; //2的31次方-1; 
    }
    dis[s] = 0;
    int pos = s;
    while (!vis[pos]) {
        ll MIN = 2147483647;
        vis[pos] = true;
        for (int i = head[pos]; ~i; i = edge[i].next) { //~i==i!=-1
            if (!vis[edge[i].u] && dis[edge[i].u] > dis[pos] + edge[i].w) {
                dis[edge[i].u] = dis[pos] + edge[i].w;
            }
        }
        if (s == 1) {           //需特判起点情况
            for (int i = 1; i <= m; i++) {
                if (dis[i] < MIN && vis[i] == 0) {
                    MIN = dis[i];
                    pos = i;
                }
            }
        }
        else {
            for (int i = 1+m; i <= m<<1; i++) {
                if (dis[i] < MIN && vis[i] == 0) {
                    MIN = dis[i];
                    pos = i;
                }
            }
        }
    }
}
int main()
{
    ios::sync_with_stdio(false);
    cin >> m >> n ;
    memset(head, -1, sizeof(head));
    for (int i = 1; i <= n; i++) {  //插入边
        int u, v, w;
        cin >> u >> v >> w;
        insert(u, v, w);
        insert(v + m, u + m, w);
    }
    dijkstra(1);         //去的情况
    for (int i = 2; i <= m; ++i) sum += dis[i];
    dijkstra(1 + m);                 //返回情况
    for (int i = 2 + m; i <= m << 1; ++i) sum += dis[i];
    cout << sum << '\n';
}


7. 洛谷P1359 租用游艇

题目描述

长江游艇俱乐部在长江上设置了n个游艇出租站1,2… n。游客可在这些游艇出租站租用游艇,

并在下游的任何一个游艇出租站归还游艇。游艇出租站i到游艇出租站j之间的租金为r(i, j)

试设计一个算法,计算出从游艇出租站1 到游艇出租站n所需的最少租金。

输入格式

第一行中有一个正整数n,表示有n个游艇出租站。接下来的n – 1行是一个半矩阵r(i, j)

输出格式

输出计算出的从游艇出租站1到游艇出租站n所需的最少租金。

样例

3

5 15

7

输出

12

思路:

由样例可得的大概意思:1到2点为5,1到3点为15,2到3为7,求1到n最短路径

于是转换为Dijkstra求1到n最短路径

#include<iostream>
#include<cstring>//memset头文件
using namespace std;
typedef long long ll;
const int maxn = 1e6 + 10;
int head[maxn], cnt;
ll dis[maxn];
bool vis[maxn];
int n, s;
struct edge1{
    int u,w;
    int next;
    edge1(){}
    edge1(int _u, int _w, int _next) {     //简化插入操作
        u = _u;
        w = _w;
        next = _next;
    }
}edge[maxn];                         //链式前向星
void insert(int u, int v, int w){//头插法
    edge[++cnt]= edge1(v,w,head[u]);// 每一个新节点的next始终指向头结点的next;
    head[u] = cnt;//头结点的next始终指向新结点
}
void dijkstra(int s) {     //dijkstra算法
    dis[s] = 0;
    int pos = s;
    while (!vis[pos]){
        ll MIN = 2147483647;
        vis[pos] = true;
        for (int i = head[pos]; ~i; i = edge[i].next){ //~i==i!=-1
            if (!vis[edge[i].u] && dis[edge[i].u] > dis[pos] + edge[i].w){
                dis[edge[i].u] = dis[pos] + edge[i].w;
            }
        }
        for (int i = 1; i <= n; i++){
            if (dis[i] < MIN && vis[i] == 0){
                MIN = dis[i];
                pos = i;
            }
        }
    }
}
int main()
{
    ios::sync_with_stdio(false);
    cin >>n;
    for (int i = 1; i <= n; i++) {
        dis[i] = 2147483647; //2的31次方-1; 
    }
    memset(head, -1, sizeof(head));
    for (int i = 1; i <= n; i++) {
        for (int j = i + 1; j <= n; j++) {
            int w;
            cin >> w;
            insert(i, j, w);
        }
    }
    dijkstra(1);
    cout << dis[n] << '\n';
}


8.洛谷P4779 【模板】单源最短路径(标准版)

思路:

涉及新知识点:堆优化(优先队列)和重载<

朴素Dijkstra 的方法是遍历所有的点通过比较找出最近的点

在这个地方可以使用 优先队列 来进行优化

首先将 优先队列 定义成 小根堆,将源点的距离初始化为 0 加入到优先队列中,

然后从这个点开始扩展。先将队列中的队头元素 ver 保存到一个临时变量中,

并将队头元素出队,然后遍历这个点的所有出边所到达的点 j,

更新所有到达的点距离源点最近的距离。

如果源点直接到 j 点的距离比源点先到 ver 点再从 ver 点到 j 点的距离大,

那么就更新 dis[j],使 dis[j] 到源点的距离最短,

并将该点到源点的距离以及该点的编号加入到优先队列中,

然后将其标记,表示该点已经确定最短距离。因为是小根堆,所以会根据距离进行排序,

距离最短的点总是位于队头。一直扩展下去,直到队列为空。

#include<iostream>
#include<cstring>//memset头文件
#include<queue>
using namespace std;
typedef long long ll;
const int maxn = 1e6 + 10;
int head[maxn], cnt;
int dis[maxn];
bool vis[maxn];
int m, n, s;
struct node {
    int dis;
    int pos;
};
struct edge1 {
    int u, w;
    int next;
    edge1() {}
    edge1(int _u, int _w, int _next) {     //简化插入操作
        u = _u;
        w = _w;
        next = _next;
    }
}edge[maxn];                         //链式前向星
void insert(int u, int v, int w) {//头插法
    edge[++cnt] = edge1(v, w, head[u]);// 每一个新节点的next始终指向头结点的next;
    head[u] = cnt;//头结点的next始终指向新结点
}
int my_sort(int l, int r)  //快排
{
    if (l >= r)
        return 0;
    int i = l, j = r;
    edge1 t, t1 = edge[l];
    while (i < j)
    {
        while (i < j && edge[j].w <= t1.w)
            j--;
        while (i < j && edge[i].w >= t1.w)
            i++;
        if (i < j) {
            t = edge[i];
            edge[i] = edge[j];
            edge[j] = t;
        }
    }
    edge[l] = edge[i];
    edge[i] = t1;
    my_sort(l, i - 1);
    my_sort(i + 1, r);
}
void dijkstra(int s) {     //dijkstra算法堆优化
    dis[s] = 0;
    queue <node>q;
    q.push(node{ 0,s });
    int flag = 1;
    while (!q.empty()) {
        node tmp = q.front();
        flag--;
        q.pop();
        int x = tmp.pos, d = tmp.dis;//因为有 重边 的缘故,所以该点可能会有冗余数据,
        if (vis[x])//遇到已经被标记的,直接 continue 
            continue;//忽略掉冗余数据继续扩展下一个点即可。
        vis[x] = 1;
        for (int i = head[x]; ~i; i = edge[i].next) {
            int y = edge[i].u;
            if (dis[y] > dis[x] + edge[i].w){
                dis[y] = dis[x] + edge[i].w;
                if (!vis[y]){
                    q.push(node{ dis[y], y });
                    flag++;
                }
            }
        }
        my_sort(1, flag);
    }
}
int main()
{
    ios::sync_with_stdio(false);
    cin >> m >> n >> s;
    for (int i = 1; i <= n; i++) {
        dis[i] = 2147483647; //2的31次方-1; 
    }
    memset(head, -1, sizeof(head));
    for (int i = 1; i <= n; i++) {  //插入边
        int u, v, w;
        cin >> u >> v >> w;
        insert(u, v, w);
    }
    dijkstra(s);
    for (int i = 1; i <= m; i++) {   //s到1...n的最短路径
        cout << dis[i] << ' ';
    }
}


简化:重载<

#include<iostream>
#include<cstring>//memset头文件
#include<queue>
using namespace std;
typedef long long ll;
const int maxn = 1e6 + 10;
int head[maxn], cnt;
int dis[maxn];
bool vis[maxn];
int m, n, s;
struct node{
    int dis;
    int pos;
    bool operator <(const node& x)const{       //重载<
        return x.dis < dis;
    }
};
struct edge1{
    int u,w;
    int next;
    edge1(){}
    edge1(int _u, int _w, int _next) {     //简化插入操作
        u = _u;
        w = _w;
        next = _next;
    }
}edge[maxn];                         //链式前向星
void insert(int u, int v, int w){//头插法
    edge[++cnt]= edge1(v,w,head[u]);// 每一个新节点的next始终指向头结点的next;
    head[u] = cnt;//头结点的next始终指向新结点
}
void dijkstra(int s) {     //dijkstra算法堆优化
    dis[s] = 0;
   std::priority_queue <node>q;
    q.push(node{ 0,s });
    while (!q.empty()) {
        node tmp = q.top();
        q.pop();
        int x = tmp.pos, d = tmp.dis;
        if (vis[x])
            continue;
        vis[x] = 1;
        for (int i = head[x]; ~i; i = edge[i].next)
        {
            int y = edge[i].u;
            if (dis[y] > dis[x] + edge[i].w)
            {
                dis[y] = dis[x] + edge[i].w;
                if (!vis[y])
                {
                    q.push(node { dis[y], y });
                }
            }
        }
    }
}
int main()
{
    ios::sync_with_stdio(false);
    cin >> m >> n >> s;
    for (int i = 1; i <= n; i++) {
        dis[i] = 2147483647; //2的31次方-1; 
    }
    memset(head, -1, sizeof(head));
    for (int i = 1; i <= n; i++) {  //插入边
        int u, v, w;
        cin >> u >> v >> w;
        insert(u, v, w);
    }
    dijkstra(s);
    for (int i = 1; i <= m; i++){   //s到1...n的最短路径
        cout << dis[i] << ' ';
    }
}



版权声明:本文为m0_75027890原创文章,遵循 CC 4.0 BY-SA 版权协议,转载请附上原文出处链接和本声明。