數據結構——最短路(BFS,Dijkstra,Floyd)

完整版可以看我的最短路問題模版總結_稠密圖最短路-CSDN博客

考研數據結構只考BFS,Dijkstra和Floyd

下面代碼以Acwing模板題為例

BFS代碼

適用類型:

1.單源最短路徑

2.無權圖

3.不適用于帶權圖和負權回路圖

//Acwing走迷宮bfs
#include<bits/stdc++.h>using namespace std;const int N = 110;typedef pair<int,int> PII;int g[N][N];bool st[N][N];int dx[4]={-1,0,1,0};int dy[4]={0,-1,0,1};int n,m;int ans[N][N];void bfs(int x,int y)
{queue<PII> q;q.push({x,y});while(!q.empty()){auto t = q.front();q.pop();for(int i=0;i<4;i++){int nex = t.first + dx[i];int ney = t.second + dy[i];if(nex>=1&&nex<=n&&ney>=1&&ney<=m&&!st[nex][ney]&&g[nex][ney]==0){q.push({nex,ney});ans[nex][ney]=ans[t.first][t.second]+1;st[nex][ney]=true;}}}
}int main()
{cin>>n>>m;for(int i=1;i<=n;i++){for(int j=1;j<=m;j++){cin>>g[i][j];}}bfs(1,1);cout<<ans[n][m]<<endl;return 0;
}

Dijkstra代碼(O(n^2))

適用類型:

1.單源最短路徑

2.正權圖

3.不適用于負權圖和負權回路圖

#include <bits/stdc++.h>using namespace std;
#define fs first
#define sc second
#define endl '\n'
#define all(x) x.begin(), x.end()
typedef long long ll;
typedef pair<int, int> PII;const int N = 510;int dist[N];//dist[i]表示i號點到源點的距離int st[N];//表示一個最短路徑的點集合 若為1表示在集合中 若為0表示不在集合中 全局初始為0int g[N][N];//鄰接矩陣存儲int n,m;//點和邊int Dijkstra()
{//初始化memset(dist,0x3f,sizeof(dist));//memset按字節賦值 賦值完是0x3f3f3f3fdist[1]=0;for(int i=1;i<=n;i++){int t=-1;for(int j=1;j<=n;j++){if(!st[j]&&(t==-1||dist[j]<dist[t])){t=j;}}//內層循環執行完后便找到了在集合st外距離源點(這里默認為1)最近的點st[t]=1;//加入集合//用t來更新距離for(int k=1;k<=n;k++){dist[k]=min(dist[k],dist[t]+g[t][k]);}}if(dist[n]==0x3f3f3f3f)return -1;//1——>n不連通return dist[n];
}int main(){cin.tie(0);cout.tie(0);ios::sync_with_stdio(0);memset(g,0x3f,sizeof(g));cin>>n>>m;for(int i=0;i<m;i++){int a,b,c;cin>>a>>b>>c;g[a][b]=min(g[a][b],c);}cout<<Dijkstra()<<endl;return 0;
}

Floyd代碼 (O(n^3))

適用類型:

1.多源最短路徑

2.正、負權圖

3.適用于負權,不適用于負權回路圖

#include <iostream>
using namespace std;const int N = 210, M = 2e+10, INF = 1e9;int n, m, k, x, y, z;
int d[N][N];void floyd() {for(int k = 1; k <= n; k++)for(int i = 1; i <= n; i++)for(int j = 1; j <= n; j++)d[i][j] = min(d[i][j], d[i][k] + d[k][j]);
}int main() {cin >> n >> m >> k;for(int i = 1; i <= n; i++)for(int j = 1; j <= n; j++)if(i == j) d[i][j] = 0;else d[i][j] = INF;while(m--) {cin >> x >> y >> z;d[x][y] = min(d[x][y], z);//注意保存最小的邊}floyd();while(k--) {cin >> x >> y;if(d[x][y] > INF/2) puts("impossible");else cout << d[x][y] << endl;}return 0;
}

本文來自互聯網用戶投稿,該文觀點僅代表作者本人,不代表本站立場。本站僅提供信息存儲空間服務,不擁有所有權,不承擔相關法律責任。
如若轉載,請注明出處:http://www.pswp.cn/diannao/73817.shtml
繁體地址,請注明出處:http://hk.pswp.cn/diannao/73817.shtml
英文地址,請注明出處:http://en.pswp.cn/diannao/73817.shtml

如若內容造成侵權/違法違規/事實不符,請聯系多彩編程網進行投訴反饋email:809451989@qq.com,一經查實,立即刪除!

相關文章

ftp替代品,如何提升數據交換的安全性與高效性?

文件傳輸協議&#xff08;FTP&#xff09;是一個跨平臺的、簡單且易于實現的協議&#xff0c;用于在網絡上的服務器和客戶端之間傳輸文件&#xff0c;也是企業會經常選擇的一種傳輸方式。 業務場景一&#xff1a; 基于信息相關安全要求&#xff0c;醫院會采用防火墻、網閘等將…

單片機開發資源分析的實戰——以STM32G431RBT6為例子的單片機資源分析

目錄 第一點&#xff1a;為什么叫STM32G431RBT6 從資源手冊拿到我們的對STM32G431RBT6的資源描述 第二件事情&#xff0c;關心我們的GPIO引腳輸出 第三件事情&#xff1a;去找對應外設的說明部分 第一點&#xff1a;為什么叫STM32G431RBT6 對于命名規則不太熟悉的朋友看這里…

Android PC 要來了?Android 16 Beta3 出現 Enable desktop experience features 選項

在之前的 《Android 桌面窗口新功能推進》 我們就聊過&#xff0c;Google 就一直在努力改進 Android 的內置桌面模式&#xff0c;例如添加了適當的窗口標題、捕捉窗口的能力、懸停選項、窗口大小調整、最小化支持、app-to-web 等。 比如在搭載 Android 15 QPR 1 Beta 2 的 Pix…

IP關聯是什么?怎么避免?

在跨境電商的道路上&#xff0c;大家好&#xff01;今天想和大家聊一聊一個非常重要的話題&#xff0c;那就是IP關聯的問題。在商業活動中&#xff0c;了解如何避免IP關聯對保護我們寶貴的商鋪至關重要。接下來&#xff0c;我們將深入探討IP關聯的概念、影響及如何有效防止這一…

行為模式---狀態模式

概念 狀態模式是一種行為模式&#xff0c;用于在內部狀態改變的時候改變其行為。它的核心思想就是允許一個對象在其內部狀態改變的時候改變它的行為。狀態模式通過將對象的狀態封裝成獨立的類&#xff0c;并將其行為委托給當前的狀態對象&#xff0c;從而使得對象行為隨著狀態…

目標檢測中衡量模型速度和精度的指標:FPS和mAP

“FPS”和“mAP”分別衡量了模型的速度和精度。 FPS&#xff08;Frames Per Second&#xff09; 定義&#xff1a;FPS是“每秒傳輸幀數”的縮寫&#xff0c;用于衡量計算機視覺系統&#xff08;如目標檢測、圖像識別等&#xff09;的實時性能。它表示系統每秒鐘能夠處理的圖像…

網頁復印機:只需一個網址,一鍵克隆任何網站!(可根據需求生成/優化相關代碼)

文章目錄 ?? 介紹 ???? 演示環境 ???? 網頁代碼克隆神器:一鍵復刻精美設計,提升前端開發效率 ????? 使用?? 相關鏈接 ???? 介紹 ?? 每天對著別人的精美網站漏出羨慕的眼神,卻苦于自己的前端技術不夠硬,難以完美復刻?或者為了趕項目進度,不得不重復…

go語言中數組、map和切片的異同

在Go語言中&#xff0c;數組、切片&#xff08;slice&#xff09;和映射&#xff08;map&#xff09;是三種常用的數據結構&#xff0c;它們在用途和特性上有顯著差異。以下是它們的異同總結&#xff1a; 相同點 集合類型&#xff1a;三者都用于存儲一組數據。 元素訪問&#…

前端Vue3圖像編輯功能(并生成mask圖)

存在一個需求同豆包的圖像生成的區域重繪功能,類似與下面這種 拆解一下需求, 1、鼠標移動上圖像畫面時出現跟隨鼠標移動的空心圓形,移出圖像畫面、鼠標點擊后、鼠標按下移動時消失,鼠標松開再次出現。 2、鼠標按下出現圓形透明顏色大小同空心圓形、鼠標按下移動形成軌跡,…

解決:ModuleNotFoundError: No module named ‘_sqlite3‘

報錯&#xff1a; from _sqlite3 import * ModuleNotFoundError: No module named _sqlite3安裝sqlite3支持組件: sudo apt-get install libsqlite3-dev進入之前下載的python包下&#xff0c;重新編譯和安裝Python ./configure --enable-loadable-sqlite-extensions make &a…

【Go語言圣經3.6】

目標 概念 常量與變量的主要區別在于&#xff1a; 不可變性&#xff1a;常量在聲明后其值就固定下來&#xff0c;不能再被修改。這保證了程序運行時不會因意外修改而導致錯誤。 使用不可變數據&#xff08;例如數學常數 π&#xff09;可以避免意外修改帶來的問題 編譯期計算…

基于x11vnc的ubuntu遠程桌面

1、安裝VNC服務 sudo apt install x11vnc -y2、創建連接密碼 sudo x11vnc -storepasswd3、安裝lightdm服務 x11vnc 在 默認的 GDM3 中不起作用&#xff0c;因此需要使用 lightdm 桌面管理環境 sudo apt install lightdm -y切換至lightdm&#xff0c;上一步已經切換則跳過該…

leetcode日記(105)買賣股票的最佳時機Ⅱ

原本以為是一個很難想的動態規劃&#xff0c;沒想到是最簡單的貪心…… 如果實在想不出就畫個折線圖&#xff0c;只買上漲的就行了&#xff0c;所有上漲的段都取到。 真的沒想到會這么簡單…… class Solution { public:int maxProfit(vector<int>& prices) {int …

手寫發布訂閱模式

手寫實現一個簡易的發布訂閱模式&#xff0c;通常有以下幾個關鍵點&#xff1a; 訂閱&#xff08;subscribe&#xff09;&#xff1a;用戶訂閱特定的事件&#xff0c;當該事件觸發時&#xff0c;執行與事件關聯的回調函數。 發布&#xff08;publish&#xff09;&#xff1a;當…

docker入門篇

使用docker可以很快部署相同的環境,這也是最快的環境構建,接下來就主要對docker中的基礎內容進行講解.Docker 是一個用于開發、交付和運行應用程序的開源平臺&#xff0c;它可以讓開發者將應用程序及其依賴打包到一個容器中&#xff0c;然后在任何環境中運行這個容器&#xff0…

Qt Widgets、Qt Quick

一、核心概念 ?Qt Widgets? Qt框架中的傳統桌面UI開發組件庫&#xff0c;基于C實現&#xff0c;提供按鈕、文本框等控件?。適用于需要深度集成操作系統底層功能或復雜業務邏輯的桌面應用?。 ?Qt Quick? QML的標準庫和工具包&#xff0c;提供預置的視覺組件&#xff08;如…

LinuX---Shell正則表達式

正則表達式 正則表達式使用單個字符串來描述、匹配一系列符合某個語法規則的字符串。在很多文本編輯器里&#xff0c;正則表達式通常被用來檢索、替換那些符合某個模式的文本。在Linux中&#xff0c;grep&#xff0c;sed&#xff0c;awk等命令都支持通過正則表達式進行模式匹配…

nginx配置txt文件點擊鏈接后下載

手上有一個txt文件&#xff0c;上傳到文件服務器后&#xff0c;點擊路徑是在瀏覽器里直接打開了&#xff0c;用戶需要的是下載到本地 nginx新增配置 location ~* /ExcelDownload/envScript/(.\.txt) {add_header Content-Disposition "attachment; filename$1";add…

相機光學(四十七)——相紙材質

1. 光面相紙 光面相紙表面光滑&#xff0c;亮度高&#xff0c;反光性好&#xff0c;能夠呈現出清晰、鮮艷的圖像效果&#xff0c;適合用于表現色彩艷麗、反差要求較高的題材&#xff0c;如產品照、藝術照和風景照。然而&#xff0c;這種相紙容易沾上指紋和灰塵。 2. 絨面相紙…

LabVIEW 線性擬合

該 LabVIEW 程序實現了 線性擬合&#xff08;Linear Fit&#xff09;&#xff0c;用于計算給定一組數據點的斜率&#xff08;Slope&#xff09;和截距&#xff08;Intercept&#xff09;&#xff0c;并將結果可視化于 XY Graph 中。本案例適用于數據擬合、實驗數據分析、傳感器…