专栏首页Don的成长史【蓝桥杯】ALGO-5 最短路

【蓝桥杯】ALGO-5 最短路

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

本文链接:https://blog.csdn.net/weixin_42449444/article/details/102962166

题目描述:

给定一个n个顶点,m条边的有向图(其中某些边权可能为负,但保证没有负环)。请你计算从1号点到其他点的最短路(顶点从1到n编号)。

输入描述:

第一行两个整数n, m。接下来的m行,每行有三个整数u, v, l,表示u到v有一条长度为l的边。(1 <= n <= 20000,1 <= m <= 200000,-10000 <= l <= 10000),保证从任意顶点都能到达其他所有顶点。

输出描述:

输出共n-1行,第i行表示1号点到i+1号点的最短路。

输入样例:

3 3
1 2 -1
2 3 -1
3 1 2

输出样例

-1
-2

解题思路:

Dijkstra算法无法判断含负权边的图的最短路,Floyd算法时间复杂度为O(n³),故均不考虑。这里用Bellman-Ford算法,它能在存在负权边的情况下解决单源点最短路径问题。

AC代码:

#include <bits/stdc++.h>
using namespace std;
#define Up(i,a,b) for(int i = a; i <= b; i++)
#define ms(a,x) memset(a,x,sizeof(a))
const int INF = 0x3f3f3f3f;
const int maxn = 200001;

int u[maxn],v[maxn],w[maxn];
int d[maxn];    //记录起点1到各点的最短距离

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0),cout.tie(0);
    ms(d,INF);  //初始化图的信息
    d[1] = 0;   //1到自身的距离为0
    int n,m;    //顶点数n,边数m
    cin >> n >> m;
    Up(i,1,m)
    {
        cin >> u[i] >> v[i] >> w[i];
    }
    Up(i,1,n-1)
    {
        bool flag = false;
        Up(j,1,m)
        {
            if(d[v[j]] > d[u[j]]+w[j])
            {
                d[v[j]] = d[u[j]]+w[j];   //更新最短路
                flag = true;
            }
        }
        if(!flag) break;   //若不再更新最短路,提前退出循环
    }
    Up(i,2,n)
    {
        cout << d[i] << endl;
    }
    return 0;
}

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

我来说两句

0 条评论
登录 后参与评论

相关文章

  • 【蓝桥杯】PREV-37 分巧克力

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

    喜欢ctrl的cxk
  • 【蓝桥杯】BASIC-30 阶乘计算

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

    喜欢ctrl的cxk
  • 【蓝桥杯】ADV-136 大数加法

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

    喜欢ctrl的cxk
  • 图片操作系列 —(2)手势旋转图片

    在上次的文章:图片操作系列 —(1)手势缩放图片功能中,我们已经学会了如何用手势来对图片进行缩放。这次我们继续来看第二个操作,那就是如何用手势来旋转图片。

    青蛙要fly
  • Dijkstra算法--单源最短路径

    在http://blog.csdn.net/hacker_zhidian/article/details/54898064这一篇博客中总结了一下在求图的最短路中...

    指点
  • 快速学习-Seata--分布式事务

    事务指的就是一个操作单元,在这个操作单元中的所有操作最终要保持一致的行为,要么所有操作 都成功,要么所有的操作都被撤销。简单地说,事务提供一种“要么什么都不做,...

    cwl_java
  • 线程的锁

    其中,AbstractQueuedSynchronizer为AQS,而且我们后面要讲的Lock显式锁的内部类(ReentrantLock、 ReadWriteL...

    晚上没宵夜
  • 乐视2017暑假实习生笔试题二分查找之JAVA实现

    试题 对一个含有20个元素的有序数组做二分查找,数组起始下标为1,则查找A[2]的比较序列的下标为() A. 9,5,4,2 B. 10, 5, 3, 2 C....

    小柒2012
  • 【leetcode】Longest Valid Parentheses

    Given a string containing just the characters '(' and ')', find the length of th...

    阳光岛主
  • 2017了,回家前 "年末" 分享:下雨,飘雪,红包雨,碰撞球,自定义View

    (本博客为原创:https://cloud.tencent.com/developer/user/1148436/activities) 目录:   效果展示 ...

    林冠宏-指尖下的幽灵

扫码关注云+社区

领取腾讯云代金券