單源最短路的建圖方式

1129. 熱浪 - AcWing題庫

這道題可以有三種方法來做，樸素版的dijkstra、堆優化版的dijkstra和spfa算法

（1）spfa算法?

?這里的隊列用循環隊列，而不是像模板那樣用普通隊列是因為它的隊列長度不確定

import java.util.*;public class Main{static int N = 2510, M = 2 * 6200 + 10;static int n, m, S, T, idx;static int[] dist = new int[N];static int[] q = new int[N];static int[] h = new int[N], ne = new int[M], e = new int[M], w = new int[M];//鄰接表static boolean[] st = new boolean[N];//鄰接表存儲public static void add(int a, int b, int c){e[idx] = b;w[idx] = c;ne[idx] = h[a];h[a] = idx ++;}public static void spfa(){Arrays.fill(dist, 0x3f3f3f3f);dist[S] = 0;int hh = 0, tt = 1;//循環隊列q[0] = S;st[S] = true;//在隊列里面while(hh != tt){//循環隊列判斷為空的條件int t = q[hh ++];if(hh == N) hh = 0;st[t] = false;//取出了這個元素for(int i = h[t]; i != -1; i = ne[i]){int j = e[i];if(dist[j] > dist[t] + w[i]){dist[j] = dist[t] + w[i];if(!st[j]){q[tt ++] = j;//加入循環隊列if(tt == N) tt = 0;st[j] = true;}}}}}public static void main(String[] args){Scanner sc = new Scanner(System.in);n = sc.nextInt();//點m = sc.nextInt();//邊S = sc.nextInt();//起點T = sc.nextInt();//終點//建圖Arrays.fill(h, -1);//這個一定要記得for(int i = 0; i < m; i ++){int a = sc.nextInt();int b = sc.nextInt();int c = sc.nextInt();add(a, b, c);//無向圖add(b, a, c);}spfa();System.out.print(dist[T]);}
}

（2） dijkstra堆優化算法

import java.util.*;class PII implements Comparable<PII>{int distance, num;public PII(int distance, int num){this.distance = distance;this.num = num;}public int compareTo(PII o){return distance - o.distance;}
}public class Main{static int N = 2510, M = 2 * 6200 + 10;static int n, m, S, T, idx;static int[] dist = new int[N];static int[] h = new int[N], ne = new int[M], e = new int[M], w = new int[M];//鄰接表static boolean[] st = new boolean[N];//鄰接表存儲public static void add(int a, int b, int c){e[idx] = b;w[idx] = c;ne[idx] = h[a];h[a] = idx ++;}public static void dijkstra(){PriorityQueue<PII> q = new PriorityQueue<>();//優先隊列Arrays.fill(dist, 0x3f3f3f3f);dist[S] = 0;q.offer(new PII(0, S));while(!q.isEmpty()){PII t = q.poll();int distance = t.distance;//到起點的距離int num = t.num;//點的編號if(st[num]) continue;//遍歷過了st[num] = true;//標記為遍歷過for(int i = h[num]; i != -1; i = ne[i]){int j = e[i];if(dist[j] > distance + w[i]){dist[j] = distance + w[i];if(!st[j]) q.offer(new PII(dist[j], j));}}}}public static void main(String[] args){Scanner sc = new Scanner(System.in);n = sc.nextInt();//點m = sc.nextInt();//邊S = sc.nextInt();//起點T = sc.nextInt();//終點//建圖Arrays.fill(h, -1);//這個一定要記得for(int i = 0; i < m; i ++){int a = sc.nextInt();int b = sc.nextInt();int c = sc.nextInt();add(a, b, c);//無向圖add(b, a, c);}dijkstra();System.out.print(dist[T]);}
}

1128. 信使 - AcWing題庫

????????這道題是讓我們求出指揮部到所有點的最短距離，取一個最大值，如果存在一個點距離指揮部的距離是正無窮的話，就輸出-1。?

? ? ? ? 這道題雖然是讓我們求單源最短路，但是我們也可以用多源最短路的Floyd算法來求。

Floyd算法?

import java.util.*;public class Main{static int N = 110;static int[][] dist = new int[N][N];static int n, m;public static void main(String[] args){Scanner sc = new Scanner(System.in);n = sc.nextInt();m = sc.nextInt();for(int i = 1; i <= n; i ++){for(int j = 1; j <= n; j ++){if(i == j) dist[i][j] = 0;else dist[i][j] = 0x3f3f3f3f;}}for(int i = 1; i <= m; i ++){int a = sc.nextInt();int b = sc.nextInt();int c = sc.nextInt();dist[a][b] = dist[b][a] = Math.min(dist[a][b], c);//防止出現重邊}//開始Floy算法for(int k = 1; k <= n; k ++){for(int i = 1; i <= n; i ++){for(int j = 1; j <= n; j ++){dist[i][j] = Math.min(dist[i][j], dist[i][k] + dist[k][j]);}}}//找到最大的那條最短路徑int res = 0;for(int i = 1; i <= n; i ++){if(dist[1][i] == 0x3f3f3f3f){res = -1;break;}res = Math.max(res, dist[1][i]);}//輸出最大值System.out.print(res);}
}

?

?1127. 香甜的黃油 - AcWing題庫

????????這道題是本質上是一個多源最短路問題，讓我們算出每個點到其他點的距離之和的最小值，但是這道題的數據很大，如果用Floyd算法會超時，所以這里我們可以用spfa算法算出n個點的情況，去一個最小值。

spfa算法?

import java.util.*;public class Main{static int N = 810, M = 3000, INF = 0x3f3f3f3f;static int n, m, p, idx;static int[] id = new int[N];//奶牛所在牧場編號static int[] q = new int[N];//循環隊列static int[] h = new int[N], e = new int[M], ne = new int[M], w = new int[M];static boolean[] st = new boolean[N];static int[] dist = new int[N];public static void add(int a, int b, int c){e[idx] = b;w[idx] = c;ne[idx] = h[a];h[a] = idx ++;}public static int spfa(int u){Arrays.fill(dist, INF);dist[u] = 0;int hh = 0, tt = 1;q[0] = u;st[u] = true;while(hh != tt){int t = q[hh ++];if(hh == N) hh = 0;st[t] = false;for(int i = h[t]; i != -1; i = ne[i]){int j = e[i];if(dist[j] > dist[t] + w[i]){dist[j] = dist[t] + w[i];if(!st[j]){q[tt ++] = j;if(tt == N) tt = 0;st[j] = true;}}}}int res = 0;for(int i = 0; i < n; i ++){int j = id[i];//奶牛所在牧場編號if(dist[j] == INF){return INF;} res += dist[j];}return res;}public static void main(String[] args){Scanner sc = new Scanner(System.in);n = sc.nextInt();p = sc.nextInt();m = sc.nextInt();Arrays.fill(h, -1);for(int i = 0; i < n; i ++){id[i] = sc.nextInt();}for(int i = 1; i <= m; i ++){int a = sc.nextInt();int b = sc.nextInt();int c = sc.nextInt();add(a, b, c);//無向圖add(b, a, c);}int res = INF;for(int i = 1; i <= p; i ++){//所有奶牛到第i個牧場的距離之和res = Math.min(res, spfa(i));}System.out.print(res);}
}

?

?1126. 最小花費 - AcWing題庫

這道題要我們求a的最少錢數，因為有100=da*w1*w2*...(其中這里的w是指1-手續費%，也就是匯率），要先da最小，那么就是說要w的乘積最大?

樸素版dijkstra算法?

import java.util.*;public class Main{static int N = 2010;static int n, m, start, end;static double[][] g = new double[N][N];//鄰接矩陣存儲邊static double[] dist = new double[N];//起點到其他點的距離static boolean[] st = new boolean[N];public static void dijkstra(){//Arrays.fill(dist, 0x3f3f3f3f);我們要求的是dist的最大值，所以這里不需要這句話dist[start] = 1;for(int i = 1; i <= n; i ++){//遍歷n次，每次找到一個int t = -1;for(int j = 1; j <= n; j ++){if(!st[j] && (t == -1 || dist[j] > dist[t])){t = j;}}st[t] = true;//標記為遍歷過for(int j = 1; j <= n; j ++){dist[j] = Math.max(dist[j], dist[t] * g[t][j]);}}}public static void main(String[] args){Scanner sc = new Scanner(System.in);n = sc.nextInt();m = sc.nextInt();for(int i = 0; i < m; i ++){int a = sc.nextInt();int b = sc.nextInt();int c = sc.nextInt();double z = (100.0 - c) / 100.0;//這里為什么取最大值？因為原本是要求c最小的，而現在的z與c的關系是相反的，所以取最大g[a][b] = g[b][a] = Math.max(g[a][b], z);//防止重邊}start = sc.nextInt();end = sc.nextInt();dijkstra();//我們求的dist是w乘積的最大值，如果想要da的最大值，就要用100來除distSystem.out.printf("%.8f", 100.0 / dist[end]);}
}

?

920. 最優乘車 - AcWing題庫

換車的最小次數=坐車的最小次數 - 1?

由于這道題所有邊的權重是1，所以可以直接用bfs，不需要用dijkstra、spfa什么的

import java.util.*;
import java.io.*;public class Main{static int N = 510;static int n, m, res, INF = 0x3f3f3f3f;static int[] q = new int[N];//用數組來模擬隊列static boolean[][] g = new boolean[N][N];//true表示連通，false表示不連通static int[] dist = new int[N];//最小坐車次數static int[] cnt = new int[N];//每條線路經過的巴士站public static void bfs(){Arrays.fill(dist, INF);dist[1] = 0;int hh = 0, tt = -1;q[++ tt] = 1;while(hh <= tt){int t = q[hh ++];//取出隊頭for(int i = 1; i <= n; i ++){if(g[t][i] && dist[i] > dist[t] + 1){dist[i] = dist[t] + 1;q[++ tt] = i;}}}}public static void main(String[] args)throws IOException{BufferedReader br = new BufferedReader(new InputStreamReader(System.in));String[] s = br.readLine().split(" ");m = Integer.parseInt(s[0]);n = Integer.parseInt(s[1]);for(int i = 0; i < m; i ++){String[] arr = br.readLine().split(" ");int len = arr.length;//這條線路經過多少個車站for(int j = 0; j < len; j ++) cnt[j] = Integer.parseInt(arr[j]);for(int j = 0; j < len; j ++){//這個車站和它后面的車站之間都連通（單程）for(int k = j + 1; k < len; k ++){g[cnt[j]][cnt[k]] = true;//連通置為true}}}bfs();if(dist[n] == INF) System.out.print("NO");else System.out.print(dist[n] - 1);}
}

?

903. 昂貴的聘禮 - AcWing題庫

用一個虛擬遠點將這些點聯系起來，建圖?

?

?

import java.util.*;public class Main{static int N = 110;static int n, m;static int[][] g = new int[N][N];//用于建圖static int[] dist = new int[N];static boolean[] st = new boolean[N];static int[] level = new int[N];//每個點的等級public static int dijkstra(int down, int up){//因為要枚舉多個區間，所以每次開始之前都要進行初始化Arrays.fill(st, false);Arrays.fill(dist, 0x3f3f3f3f);dist[0] = 0;//虛擬遠點的距離置為0//樸素版的dijkstra，因為建立了一個虛擬遠點，所以循環的時候要從0開始for(int i = 0; i <= n; i ++){int t = -1;for(int j = 0; j <= n; j ++){if(!st[j] && (t == -1 || dist[t] > dist[j])){t = j;}}st[t] = true;//更新其他點的值for(int j = 0; j <= n; j ++){if(level[j] >= down && level[j] <= up){dist[j] = Math.min(dist[j], dist[t] + g[t][j]);}}}return dist[1];}public static void main(String[] args){Scanner sc = new Scanner(System.in);m = sc.nextInt();n = sc.nextInt();//初始化for(int i = 0; i < N; i ++){Arrays.fill(g[i], 0x3f3f3f3f);}for(int i = 0; i < N; i ++){g[i][i] = 0;}//建圖for(int i = 1; i <= n; i ++){int price = sc.nextInt();level[i] = sc.nextInt();int cnt = sc.nextInt();//有幾種兌換方式g[0][i] = price;//虛擬遠點到當前點的距離（不兌換，直接購買）for(int j = 1; j <= cnt; j ++){int id = sc.nextInt();int cost = sc.nextInt();g[id][i] = cost;//兌換物品到當前點的距離}}int res = 0x3f3f3f3f;//枚舉等級的左端點，找到最小的等級，因為我們一定要將第一個點包含在內for(int i = level[1] - m; i <= level[1]; i ++) res = Math.min(res, dijkstra(i, i + m));System.out.print(res);}
}

?

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

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

相關文章

mysql 大數據量分批添加索引

mysql 大數據量分批添加索引

先在測試環境測試&#xff0c;沒問題再上生產環境&#xff0c;避免生產環境數據庫負載過多而崩潰 創建存儲過程 DELIMITER //CREATE PROCEDURE batch_add_index_to_email() BEGINDECLARE done INT DEFAULT FALSE;DECLARE start_id INT DEFAULT 0;DECLARE end_id INT;DECLARE …
閱讀更多...
貝葉斯優化CNN分類（matlab代碼）

貝葉斯優化CNN分類（matlab代碼）

貝葉斯優化CNN分類matlab代碼 數據為Excel分類數據集數據。 數據集劃分為訓練集、驗證集、測試集&#xff0c;比例為8:1:1 數據處理: 在數據加載后&#xff0c;對數據進行了劃分&#xff0c;包括訓練集、驗證集和測試集&#xff0c;這有助于評估模型的泛化能力。 數據標準化…
閱讀更多...
13.7隊列的實戰（通過鏈表實現）

13.7隊列的實戰（通過鏈表實現）

學個二叉樹&#xff0c;又要用上隊列的代碼&#xff0c;上學期學的隊列忘光光了&#xff0c;這不沒辦法回來復習咯 代碼&#xff1a; #include <stdio.h> #include <stdlib.h>typedef int ElemType; typedef struct LinkNode{ElemType data;struct LinkNode *next…
閱讀更多...
動態規劃（算法競賽、藍橋杯）--樹形DP沒有上司的舞會

動態規劃（算法競賽、藍橋杯）--樹形DP沒有上司的舞會

1、B站視頻鏈接&#xff1a;E17 樹形DP Luogu P1352 沒有上司的舞會_嗶哩嗶哩_bilibili 題目鏈接&#xff1a;沒有上司的舞會 - 洛谷 #include <bits/stdc.h> using namespace std; const int N6010; int n; int w[N]; vector<int>a[N];//鄰接表 bool fa[N]; int…
閱讀更多...
011 Linux_線程概念與創建

011 Linux_線程概念與創建

前言 本文將會向你介紹線程的概念&#xff0c;以及線程是怎么被創建的 線程概念 一、進程是承擔系統資源的基本實體&#xff0c;線程是cpu調度的基本單位 首先&#xff0c;地址空間在邏輯上相當于進程的資源窗口&#xff0c; 每個進程都有這樣一個資源窗口。通過地址空間頁…
閱讀更多...
工控傳感器選型原則及舉例說明

工控傳感器選型原則及舉例說明

工控傳感器選型原則及舉例說明 前言選型原則知識儲備光電傳感器接近開關和行程開關磁性開關模擬量傳感器類型及使用范圍數字量傳感器類型及使用范圍 選型舉例食品包裝箱運輸過程中的檢測有無倉庫提升伺服的極限位檢測產品高度檢測 前言 這里僅以數字量和模擬量信號的傳感器舉例…
閱讀更多...
Vue源碼系列講解——實例方法篇【二】(事件相關方法)

Vue源碼系列講解——實例方法篇【二】(事件相關方法)

目錄 0.前言 1. vm.$on 1.1 用法回顧 1.2 內部原理 2. vm.$emit 2.1 用法回顧 2.2 內部原理 3. vm.$off 3.1 用法回顧 3.2 內部原理 4. vm.$once 4.1 用法回顧 4.2 內部原理 0.前言 與事件相關的實例方法有4個&#xff0c;分別是vm.$on、vm.$emit、vm.$off和vm.$o…
閱讀更多...
前端面試知識點合集

前端面試知識點合集

原型和原型鏈 任何函數都可以作為構造函數。當該函數通過 new 關鍵字調用的時候&#xff0c;就稱之為構造函數。 var Parent function(){}//定義一個函數&#xff0c;那它只是一個普通的函數&#xff0c;不能稱它為構造函數var instance new Parent(); //這時這個Parent就不…
閱讀更多...
C#理論 —— WPF 應用程序Console 控制臺應用

C#理論 —— WPF 應用程序Console 控制臺應用

文章目錄 1. WPF 應用程序1.1 工程創建1.2 控件1.2.1 控件的公共屬性1.2.1 TextBox 文本框1.2.1 Button 按鈕 *. Console 控制臺應用1.1 工程創建 1. WPF 應用程序 1.1 工程創建 Visual Studio 中新建項目 - 選擇WPF 應用程序&#xff1b; 1.2 控件 1.2.1 控件的公共屬性 …
閱讀更多...
如何備份和恢復MySQL數據庫？有哪些常見的備份工具和策略？

如何備份和恢復MySQL數據庫？有哪些常見的備份工具和策略？

如何備份和恢復MySQL數據庫&#xff1f;有哪些常見的備份工具和策略&#xff1f; 在數據庫管理中&#xff0c;備份和恢復是非常重要的環節&#xff0c;它們保障了數據的安全性和可恢復性。對于MySQL這樣的關系型數據庫管理系統&#xff0c;了解并實施有效的備份策略至關重要。…
閱讀更多...
Linux網絡編程——網絡基礎

Linux網絡編程——網絡基礎

Linux網絡編程——網絡基礎 1. 網絡結構模式1.1 C/S 結構1.2 B/S 結構 2. MAC 地址3. IP地址3.1 簡介3.2 IP 地址編址方式 4. 端口4.1 簡介4.2 端口類型 5. 網絡模型5.1 OSI 七層參考模型5.2 TCP/IP 四層模型 6. 協議6.1 簡介6.2 常見協議6.3 UDP 協議6.4 TCP 協議6.5 IP 協議6…
閱讀更多...
【兔子機器人】根據自身機器人參數修改simulink模型

【兔子機器人】根據自身機器人參數修改simulink模型

關節電機 機體初始高度 &#xff01;&#xff01;&#xff01;接下來嘗試修改各腿的坐標朝向
閱讀更多...
LeetCode54題：螺旋矩陣（python3）

LeetCode54題：螺旋矩陣（python3）

路徑的長度即為矩陣中的元素數量&#xff0c;當路徑的長度達到矩陣中的元素數量時即為完整路徑&#xff0c;將該路徑返回。 循環打印&#xff1a; “從左向右、從上向下、從右向左、從下向上” 四個方向循環打印。 class Solution:def spiralOrder(self, matrix: List[List[i…
閱讀更多...
怎么對App進行功能測試

怎么對App進行功能測試

測試人員常被看作是bug的尋找者&#xff0c;但你曾想過他們實際是如何開展測試的嗎&#xff1f;你是否好奇他們究竟都做些什么&#xff0c;以及他們如何在一個典型的技術項目中體現價值&#xff1f;本文將帶你經歷測試人員的思維過程&#xff0c;探討他們測試app時的各種考慮. …
閱讀更多...
Android和Linux的嵌入式開發差異

Android和Linux的嵌入式開發差異

最近開始投入Android的懷抱。說來慚愧&#xff0c;08年就聽說這東西&#xff0c;當時也有同事投入去看&#xff0c;因為惡心Java&#xff0c;始終對這玩意無感&#xff0c;沒想到現在不會這個嵌入式都快要沒法搞了。為了不中年失業&#xff0c;所以只能回過頭又來學。 首先還是…
閱讀更多...
虛擬內存與mmap,brk

虛擬內存與mmap,brk

虛擬內存與mmap,brk 基本概念及相關術語 1.1 基本概念 虛擬內存使得應用程序認為它擁有連續的可用的內存&#xff08;一個連續完整的地址空間&#xff09;&#xff0c;而實際上&#xff0c;它通常是被分隔成多個物理內存碎片&#xff0c;還有部分暫時存儲在外部磁盤存儲器上&…
閱讀更多...
【C語言】linux內核generic_xdp_tx

【C語言】linux內核generic_xdp_tx

一、中文注釋 /* 在執行通用XDP時&#xff0c;我們必須繞過qdisc層和網絡挖掘點&#xff0c;* 以匹配驅動內XDP的行為。*/ void generic_xdp_tx(struct sk_buff *skb, struct bpf_prog *xdp_prog) {struct net_device *dev skb->dev; // 獲取skb對應的網絡設備struct netd…
閱讀更多...
面試高頻率問答題目

面試高頻率問答題目

索引&#xff1a; 主鍵索引&#xff1a;表的id &#xff08;唯一 且 不能為空&#xff09; 唯一索引&#xff1a;表User 假設有account 字段 &#xff0c;用戶名不重復 &#xff08;唯一 可以為空&#xff09; 復合索引&#xff1a;where() 的條件 用戶名&#xff0c;密碼 …
閱讀更多...
MySQL：函數

MySQL：函數

提醒&#xff1a; 設定下面的語句是在數據庫名為 db_book里執行的。 創建user_info表 注意&#xff1a;pwd為密碼字段&#xff0c;這里使用了VARCHAR(128)類型&#xff0c;為了后面方便對比&#xff0c;開發項目里一般使用char(32)&#xff0c;SQL語句里使用MD5加密函數 USE db…
閱讀更多...
【博圖TIA-Api】通過Excel自動新建文件夾和導入FB塊

【博圖TIA-Api】通過Excel自動新建文件夾和導入FB塊

【博圖TIA-Api】通過Excel自動新建文件夾和導入FB塊 說明思路準備獲取Excel表格內文件名和FB塊名等信息新建文件夾部分篩分獲取的文件夾數據&#xff0c;去掉重復內容創建文件夾 導入FB塊導出FB塊的xml文件查找需要放置的文件夾導入塊 說明 續上一篇文章&#xff0c;這次是根據…
閱讀更多...
最新文章

Copyright @ 2022~2023