图论·Day01

P3371
P4779

P3371 【模板】单源最短路径（弱化版）

注意的点：

  • 边有重复，选择最小边！
  • 对于SPFA算法容易出现重大BUG，没有负权值的边时不要使用！！！

70分代码 朴素板dijsktra

  • 爆空间
#include<bits/stdc++.h>
using namespace std;
using ll = long long;
int n, m, s, u, v, w;
void solve() {
    cin >> n >> m >> s;
    vector<vector<int>>grid(n + 9, vector<int>(n + 9, INT_MAX));
    vector<int>dist(n + 9, INT_MAX);
    vector<bool>visited(n + 9, false);
    while (m--) {
        cin >> u >> v >> w;
        grid[u][v] = min(grid[u][v], w);
    }
    dist[s] = 0;
    for (int i = 1; i <= n; i++) {
        int cur = 1;
        int minDist = INT_MAX;
        for (int j = 1; j <= n; j++) {
            if (!visited[j] && dist[j] < minDist) {
                minDist = dist[j];
                cur = j;
            }
        }
        visited[cur] = true;
        for (int j = 1; j <= n; j++) {
            if (!visited[j] && grid[cur][j] != INT_MAX && dist[cur] + grid[cur][j] < dist[j]) {
                dist[j] = dist[cur] + grid[cur][j];
            }
        }
        /*cout << "select " << cur << endl;
        for (int i = 1; i <= n; i++) {
            cout << dist[i] << " ";
        }
        cout << endl;*/
    }
    for (int i = 1; i <= n; i++) {
        cout << dist[i] << " ";
    }
}
int main() {
    std::ios::sync_with_stdio(false);
    std::cin.tie(0); std::cout.tie(0);
    solve();
    return 0;
}

32分代码 SPFA

  • 因为有重复指向的边，所有理论上边数可以无穷大，O(KM)的时间复杂度不确定性极大！
#include<bits/stdc++.h>
using namespace std;
using ll = long long;
int n, m, s, u, v, w;
struct Edge {
    int v, w;
    Edge(int a, int b) :v(a), w(b) {}
};
void solve() {
    cin >> n >> m >> s;
    vector<list<Edge>>grid(n + 9, list<Edge>());
    vector<int>dist(n + 9, INT_MAX); dist[s] = 0;
    queue<Edge>q;
    while (m--) {
        cin >> u >> v >> w;
        grid[u].push_back(Edge(v, w));
    }
    q.push({ s,0 });
    while (!q.empty()) {
        Edge cur = q.front();
        q.pop();
        for (auto item : grid[cur.v]) {
            if (item.w + dist[cur.v] < dist[item.v]) {
                dist[item.v] = dist[cur.v] + item.w;
                q.push(item);
            }
        }
    }
    for (int i = 1; i <= n; i++) {
        cout << dist[i] << " ";
    }
}
int main() {
    std::ios::sync_with_stdio(false);
    std::cin.tie(0); std::cout.tie(0);
    solve();
    return 0;
}

AC代码 堆优化dijsktra

  • 重复的边不影响
#include<bits/stdc++.h>
using namespace std;
using ll = long long;
int n, m, s, u, v, w;
struct Edge {
    int v, w;
    Edge(int a, int b) :v(a), w(b) {}
};
class cmp {
public:
    bool operator()(const Edge& a, const Edge& b) {
        return a.w > b.w;//从小排序
    }
};

void solve() {
    cin >> n >> m >> s;
    vector<list<Edge>>grid(n + 9, list<Edge>());
    vector<int>dist(n + 9, INT_MAX); dist[s] = 0;
    vector<bool>visited(n + 9, false);
    priority_queue<Edge, vector<Edge>, cmp>q;
    while (m--) {
        cin >> u >> v >> w;
        grid[u].push_back(Edge(v, w));
    }
    q.push({ s,0 });
    while (!q.empty()) {
        Edge cur = q.top();
        q.pop();
        if (visited[cur.v]) {
            continue;
        }
        visited[cur.v] = true;
        for (auto item : grid[cur.v]) {
            if (!visited[item.v]&&item.w + dist[cur.v] < dist[item.v]) {
                dist[item.v] = item.w + dist[cur.v];
                q.push({ item.v,dist[item.v] });
            }
        }
    }
    for (int i = 1; i <= n; i++) {
        cout << dist[i] << " ";
    }
}
int main() {
    std::ios::sync_with_stdio(false);
    std::cin.tie(0); std::cout.tie(0);
    solve();
    return 0;
}

P1144

最短路计数

题目描述

给出一个 N N N 个顶点 M M M 条边的无向无权图，顶点编号为 1 ∼ N 1\sim N 1∼N。问从顶点 1 1 1 开始，到其他每个点的最短路有几条。

输入格式

第一行包含 2 2 2 个正整数 N , M N,M N,M，为图的顶点数与边数。

接下来 M M M 行，每行 2 2 2 个正整数 x , y x,y x,y，表示有一条连接顶点 x x x 和顶点 y y y 的边，请注意可能有自环与重边。

输出格式

共 N N N 行，每行一个非负整数，第 i i i 行输出从顶点 1 1 1 到顶点 i i i 有多少条不同的最短路，由于答案有可能会很大，你只需要输出 $ ans \bmod 100003$ 后的结果即可。如果无法到达顶点 i i i 则输出 0 0 0。

对于 100 % 100\% 100% 的数据， 1 ≤ N ≤ 1 0 6 1\le N\le10^6 1≤N≤106， 1 ≤ M ≤ 2 × 1 0 6 1\le M\le 2\times 10^6 1≤M≤2×106。

AC题解 堆优化dijsktra

  • 多一段条件判断，不加入堆但是也起到了统计作用
else if (dist[cur.v] + item.w == dist[item.v]) {
                ct[item.v] += ct[cur.v];
                ct[item.v] %= 100003;
            }

#include<bits/stdc++.h>
using namespace std;
using ll = long long;
int n, m, x, y;
struct Edge {
    int v, w;
    Edge(int a, int b) :v(a), w(b) {};
};
class cmp {
public:
    bool operator()(const Edge& a, const Edge& b) {
        return a.w > b.w;
    }
};
priority_queue<Edge,vector<Edge>,cmp>q;
void solve() {
    cin >> n >> m;
    vector<list<Edge>>grid(n+ 9, list<Edge>());
    vector<bool>visited(n+ 9, false);
    vector<int>dist(n+9, INT_MAX);
    vector<int>ct(n+9, 0);
    while (m--) {
        cin >> x >> y;
        grid[x].push_back(Edge(y, 1));
        grid[y].push_back(Edge(x, 1));
    }
    dist[1] = 0; ct[1] = 1;
    q.push({ 1,0 });
    while (!q.empty()) {
        Edge cur=q.top();
        q.pop();
       
        if (visited[cur.v]) {
            continue;
        }
        visited[cur.v] = true;

        for (auto item : grid[cur.v]) {
            if (dist[cur.v] + item.w < dist[item.v]) {
                dist[item.v] = dist[cur.v] + item.w;
                ct[item.v] = ct[cur.v];
                q.push({ item.v,dist[item.v] });
            }
            else if (dist[cur.v] + item.w == dist[item.v]) {
                ct[item.v] += ct[cur.v];
                ct[item.v] %= 100003;
            }
            
        }
    }

    //for (int i = 1; i <= n; i++) {
    //    cout << dist[i] << " ";
    //}
    for (int i = 1; i <= n; i++) {
        cout << ct[i] << endl;
    }
}
int main() {
    std::ios::sync_with_stdio(false);
    std::cin.tie(0); std::cout.tie(0);
    solve();
    return 0;
}

P5905

【模板】全源最短路（Johnson）

题目描述

给定一个包含 n n n 个结点和 m m m 条带权边的有向图，求所有点对间的最短路径长度，一条路径的长度定义为这条路径上所有边的权值和。

注意：

  1. 边权可能为负，且图中可能存在重边和自环；

  2. 部分数据卡 n n n 轮 SPFA 算法。

输入格式

第 1 1 1 行： 2 2 2 个整数 n , m n,m n,m，表示给定有向图的结点数量和有向边数量。

接下来 m m m 行：每行 3 3 3 个整数 u , v , w u,v,w u,v,w，表示有一条权值为 w w w 的有向边从编号为 u u u 的结点连向编号为 v v v 的结点。

输出格式

若图中存在负环，输出仅一行 − 1 -1 −1。

若图中不存在负环：

输出 n n n 行：令 d i s i , j dis_{i,j} disi,j​ 为从 i i i 到 j j j 的最短路，在第 i i i 行输出 ∑ j = 1 n j × d i s i , j \sum\limits_{j=1}^n j\times dis_{i,j} j=1∑n​j×disi,j​，注意这个结果可能超过 int 存储范围。

如果不存在从 i i i 到 j j j 的路径，则 d i s i , j = 1 0 9 dis_{i,j}=10^9 disi,j​=109；如果 i = j i=j i=j，则 d i s i , j = 0 dis_{i,j}=0 disi,j​=0。

右图为样例 2 2 2 给出的有向图，红色标注的边构成了负环，注意给出的图不一定连通。

Johnson算法

  • 数据溢出longlong的转换
  • h[item.v] = h[cur.v] + item.w;这段代码是Johnson算法的精髓，势能函数
  • dist[j] + h[j] - h[st]由于路径上每一个边<i,j>都加入了h[i]-h[j],所以最短距离应该要 + 末位 - 首位，才是最终距离！
#include<bits/stdc++.h>
using namespace std;
using ll = long long;
int n, m;
ll u,v,w;
void dijsktra(int st,vector<ll>dist);
struct Edge {
    ll v, w;
    Edge(ll a, ll b) :v(a), w(b) {};
};
class cmp {
public:
    bool operator()(const Edge& a, const Edge& b) {
        return a.w > b.w;
    }
};
ll inf = ll(1e9);
queue<Edge>q;
vector<int>ct(3009, 0);
vector<list<Edge>>edges(3009, list<Edge>());
vector<ll>h(3009, inf);

vector<ll>dist(3009, inf);
priority_queue<Edge, vector<Edge>, cmp>s;
bool visited[3009];
void solve() {
    cin >> n >> m;
    while(m--) {
        cin >> u >> v >> w;
        edges[u].push_back({ v,w });
    }
    for (int i = 1; i <= n; i++) {
        edges[0].push_back({ i,0 });
    }
    h[0] = 0;
    q.push({ 0,0 }); ct[0] = 1;
    while (!q.empty()) {
        Edge cur = q.front();
        q.pop();
        if (ct[cur.v] >= n) {
            cout << -1;
            return;
        }
        for (auto item : edges[cur.v]) {
            if (h[cur.v] + item.w < h[item.v]) {
                h[item.v] = h[cur.v] + item.w;
                ct[item.v] ++;
                q.push(item);              
            }
        }
    }
  /*  cout << "h" << endl;
    for (int i = 0; i <= n; i++) {
        cout << h[i]<<" ";
    }
    cout << endl;*/
    /*重组edges数组*/
    for (int i = 1; i <= n; i++) {
        for (auto& item : edges[i]) {
            item.w = item.w+h[i] - h[item.v];
        }
    }
    for (int i = 1; i <= n; i++) {
        dijsktra(i,dist);
    }
}
void dijsktra(int st,vector<ll>dist) {
    memset(visited, false, sizeof(visited));
    dist[st] = 0; s.push({ st,0 });
    while (!s.empty()) {
        Edge cur = s.top();
        s.pop();

        if (visited[cur.v]) {
            continue;
        }
        visited[cur.v] = true;

        for (auto item : edges[cur.v]) {
            if (!visited[item.v]&&dist[cur.v] + item.w < dist[item.v]) {
                dist[item.v] = item.w+ dist[cur.v];
                s.push({ item.v,dist[item.v] });
            }
        }
    }
    /*for (int i = 1; i <= n; i++) {
        cout << dist[i] << " ";
    }
    cout << endl;*/
    ll ans = 0;
    for (int j = 1; j <= n; j++) {
        if (dist[j] == inf) {
            ans += ll(j) * dist[j];
        }
        else {
            ans += ll(j) * (dist[j] + h[j] - h[st]);
        }
    }
    cout << ans << endl;
}
int main() {
    std::ios::sync_with_stdio(false);
    std::cin.tie(0); std::cout.tie(0);
    solve();
    return 0;
}

今日总结

  • dijsktra不能用于负权值
  • Bellman可以用于检测负权回路
  • SFPA算法不要轻易用！容易爆死！
  • Floyd 算法时间复杂度O(n3),dijsktra O(mlogm),Johnson算法时间复杂度接近 O(nmlogn)，相当于用SFPA扫除了dijsktra不能求负权值边的障碍，最终还是要归结于dijsktra算法堆优化版来！说人话就是Bellman和SFPA太慢，dijsktra用不了，所以采用Johnson算法！

本文来自互联网用户投稿，该文观点仅代表作者本人，不代表本站立场。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如若转载，请注明出处：/a/787519.html

如若内容造成侵权/违法违规/事实不符，请联系我们进行投诉反馈qq邮箱809451989@qq.com，一经查实，立即删除！

相关文章

打卡第7天-----哈希表

打卡第7天-----哈希表

继续坚持✊，我现在看到leetcode上的题不再没有思路了，真的是思路决定出路，在做题之前一定要把思路梳理清楚。 一、四数相加 leetcode题目编号：第454题.四数相加II 题目描述： 给定四个包含整数的数组列表 A , B , C , D ,计算有多少个元组 (i, j, k, l) ，使得 A[i] + B[j…
阅读更多...
蚁群算法（Ant Colony Optimization，ACO）讲解+代码实现

蚁群算法（Ant Colony Optimization，ACO）讲解+代码实现

1.蚁群算法来源 蚁群算法&#xff08;Ant Colony Optimization&#xff0c;简称ACO&#xff09;是一种模拟自然界中蚂蚁寻找食物路径行为的优化算法&#xff0c;主要用于解决组合优化问题。它的灵感来源于意大利学者Marco Dorigo在1992年提出的蚂蚁系统模型。 蚁群算法的灵感来…
阅读更多...
应急响应——勒索病毒

应急响应——勒索病毒

先上搜索引擎上搜 也可以用360来杀 但是都无法解密 可以解密的&#xff1a; linux
阅读更多...
LeNet原理及代码实现

LeNet原理及代码实现

目录 1.原理及介绍 2.代码实现 2.1model.py 2.2model_train.py 2.3model.test.py 1.原理及介绍 2.代码实现 2.1model.py import torch from torch import nn from torchsummary import summaryclass LeNet(nn.Module):def __init__(self):super(LeNet, self).__init__…
阅读更多...
uniapp 去掉小数末尾多余的0

uniapp 去掉小数末尾多余的0

文章目录 在uniapp或者一般的JavaScript环境中&#xff0c;要去掉小数末尾的0&#xff0c;可以使用以下几种方法&#xff1a; 使用parseFloat()函数 let num 123.4500; let result parseFloat(num); console.log(result); // 输出: 123.45字符串处理 将数字转换为字符串&am…
阅读更多...
02day-C++学习(const 指针与引用的关系 inline nullptr)

02day-C++学习(const 指针与引用的关系 inline nullptr)

02day-C学习 1. 使用const注意事项 注意事项 • 可以引⽤⼀个const对象&#xff0c;但是必须⽤const引⽤。const引⽤也可以引⽤普通对象&#xff0c;因为对象的访 问权限在引⽤过程中可以缩⼩&#xff0c;但是不能放⼤。 • 不需要注意的是类似 int& rb a3; double d 1…
阅读更多...
代码随想录——合并区间（Leecode LCR74）

代码随想录——合并区间（Leecode LCR74）

题目链接 贪心 排序 class Solution {public int[][] merge(int[][] intervals) {ArrayList<int[]> res new ArrayList<>();// 先将数组按照左区间排序Arrays.sort(intervals, new Comparator<int[]>() {public int compare(int[] intervals1, int[] in…
阅读更多...
模板语法之插值语法{{}}——01

模板语法之插值语法{{}}——01

<主要研究&#xff1a;{{ 这里可以写什么}} 1.在data中声明的变量函数都可以 2.常量 3.只要是合法的JavaScript的表达式&#xff0c;都可以 4. 模板表达式都被放在沙盒中&#xff0c;只能访问全局变量的一个白名单&#xff0c;如 Math 和 Date <body> <div i…
阅读更多...
STM32智能仓库管理系统教程

STM32智能仓库管理系统教程

目录 引言环境准备智能仓库管理系统基础代码实现&#xff1a;实现智能仓库管理系统 4.1 数据采集模块 4.2 数据处理与控制算法 4.3 通信与网络系统实现 4.4 用户界面与数据可视化应用场景&#xff1a;仓库管理与优化问题解决方案与优化收尾与总结 1. 引言 智能仓库管理系统通…
阅读更多...
深入理解循环神经网络（RNN）

深入理解循环神经网络（RNN）

深入理解循环神经网络&#xff08;RNN&#xff09; 循环神经网络&#xff08;Recurrent Neural Network, RNN&#xff09;是一类专门处理序列数据的神经网络&#xff0c;广泛应用于自然语言处理、时间序列预测、语音识别等领域。本文将详细解释RNN的基本结构、工作原理以及其优…
阅读更多...
国际网课平台Udemy上的亚马逊云科技AWS免费高分课程和创建、维护EC2动手实践

国际网课平台Udemy上的亚马逊云科技AWS免费高分课程和创建、维护EC2动手实践

亚马逊云科技(AWS)是全球云行业最&#x1f525;火的云平台&#xff0c;在全球经济形势不好的大背景下&#xff0c;通过网课学习亚马逊云科技AWS基础备考亚马逊云科技AWS证书&#xff0c;对于找工作或者无背景转行做AWS帮助巨大。欢迎大家关注小李哥&#xff0c;及时了解世界最前…
阅读更多...
香橙派AIpro初体验：搭建无线随身NAS

香橙派AIpro初体验：搭建无线随身NAS

文章目录 1.引言2. 香橙派 AIPro概述3. 开发准备3.0 烧录镜像3.1 需要准备的硬件3.2 需要准备的软件3.3 启动并连接香橙派 AIPro3.3.1 初始化启动香橙派 AIPro3.3.2 无线连接香橙派 AIPro3.3.3.3 VNC连接香橙派 AIPro 3.4 设置固定ip3.4.1 设置开机自动连接WIFI3.4.1 设置香橙派…
阅读更多...
遍历请求后端数据引出的数组forEach异步操作的坑

遍历请求后端数据引出的数组forEach异步操作的坑

有一个列表数据&#xff0c;每项数据里有一个额外的字段需要去调另外一个接口才能拿到&#xff0c;后端有现有的这2个接口&#xff0c;现在临时需要前端显示出来&#xff0c;所以这里需要前端先去调列表数据的接口拿到列表数据&#xff0c;然后再遍历请求另外一个接口去拿到对应…
阅读更多...
springboot封装请求参数json的源码解析

springboot封装请求参数json的源码解析

源码位置&#xff1a; org.springframework.web.servlet.mvc.method.annotation.AbstractMessageConverterMethodArgumentResolver#readWithMessageConverters(org.springframework.http.HttpInputMessage, org.springframework.core.MethodParameter, java.lang.reflect.Type…
阅读更多...
Java PKI Programmer‘s Guide

Java PKI Programmer‘s Guide

一、PKI程序员指南概述 PKI Programmer’s Guide Overview Java认证路径API由一系列类和接口组成&#xff0c;用于创建、构建和验证认证路径。这些路径也被称作认证链。实现可以通过基于提供者的接口插入。 这个API基于密码服务提供者架构&#xff0c;这在《Java密码架构参考指…
阅读更多...
c＋＋入门基础篇（上）

c＋＋入门基础篇（上）

目录 前言&#xff1a; 1.c&#xff0b;&#xff0b;的第一个程序 2.命名空间 2.1 namespace的定义 2.2 命名空间使用 3.c&#xff0b;&#xff0b;输入&输出 4.缺省参数 5.函数重载 前言&#xff1a; 我们在之前学完了c语言的大部分语法知识&#xff0c;是不是意…
阅读更多...
springboot驾校管理系统-计算机毕业设计源码49777

springboot驾校管理系统-计算机毕业设计源码49777

驾校管理系统 摘 要 驾校管理系统是一个基于Spring Boot框架开发的系统&#xff0c;旨在帮助驾校提高管理效率和服务水平。该系统主要实现了用户管理、年月类型管理、区域信息管理、驾校信息管理、车辆信息管理、报名信息管理、缴费信息管理、财务信息管理、教练分配管理、更换…
阅读更多...
微搭低代码从入门到实战01创建数据源

微搭低代码从入门到实战01创建数据源

目录 1 创建数据源2 创建字段总结 很多零基础的想学习低代码开发&#xff0c;苦于没有编程的经验感觉入门困难。本次教程就按照我们日常开发的思路&#xff0c;从浅入深逐步拆解一下低代码该如何学习。 开发软件&#xff0c;不管是管理后台还是小程序&#xff0c;先需要规划好数…
阅读更多...
忘记Apple ID密码怎么退出苹果ID账号？

忘记Apple ID密码怎么退出苹果ID账号？

忘记Apple ID密码怎么退出账号&#xff1f;Apple ID对每个苹果用户来说都是必不可少的&#xff0c;没有它&#xff0c;用户就不能享受iCloud、App Store、iTunes等服务。苹果手机软件下载、丢失解锁、恢复出厂设置等都需要使用Apple ID。如果忘记Apple ID 密码&#xff0c;这会…
阅读更多...
C语言 结构体和共用体——结构体和数组的嵌套

C语言 结构体和共用体——结构体和数组的嵌套

目录 结构体和数组的相互嵌套​编辑 嵌套的结构体 嵌套结构体变量的初始化 结构体数组的定义和初始化 结构体和数组的相互嵌套 嵌套的结构体 在一个结构体内包含了另一个结构体作为其成员 嵌套结构体变量的初始化 STUDENT stu1 {100310121, " 王刚 ", M, {1991…
阅读更多...
最新文章

Copyright @ 2022~2023