g422 - PD.紅血球的快遞任務

🔗 前往 ZeroJudge 原題

題目描述

題目描述了紅血球需要從心臟（0號器官）將氧氣運送到目標細胞（b號器官），地圖上有n個器官和m條雙向血管，每條血管都有長度w。要求找到從心臟到目標細胞的最短路徑。

解題思路

這題可以使用 Dijkstra 演算法來解決。Dijkstra 演算法是一種用於在加權圖中找到單一源點到所有其他節點的最短路徑的演算法。

1. 圖的表示： 使用鄰接表 e 來表示圖。e[i] 儲存與節點 i 相鄰的節點及其對應的邊權重。
2. 初始化： 初始化一個距離陣列 dp，其中 dp[i] 儲存從起點（0號器官）到節點 i 的最短距離。將所有距離初始化為一個很大的值（例如 1e15），除了 dp[0]，它初始化為 0。
3. 優先佇列： 使用優先佇列 q 來儲存待處理的節點。優先佇列按照節點到起點的距離排序，距離較小的節點優先處理。
4. Dijkstra 演算法：
   • 將起點（0號器官）和距離 0 放入優先佇列。
   • 當優先佇列不為空時：
     • 從優先佇列中取出距離最小的節點 tmp。
     • 如果 tmp.second（到 tmp.first 的距離）大於或等於 dp[tmp.first]，則跳過該節點（因為已經找到更短的路徑）。
     • 更新 dp[tmp.first] 為 tmp.second。
     • 遍歷 tmp.first 的所有鄰居 e[tmp.first][i]：
       • 將鄰居節點 e[tmp.first][i].first 和從起點到該鄰居節點的距離 tmp.second + e[tmp.first][i].second 放入優先佇列。
5. 輸出結果： 輸出 dp[b]，即從起點到目標細胞的最短距離。

複雜度分析

• 時間複雜度: O(m log n)，其中 n 是節點數量，m 是邊的數量。這是因為 Dijkstra 演算法使用優先佇列，每次從優先佇列中取出一個節點和插入一個節點的時間複雜度都是 O(log n)，而遍歷所有邊的時間複雜度是 O(m)。
• 空間複雜度: O(n + m)，其中 n 是節點數量，m 是邊的數量。O(n) 用於儲存距離陣列 dp，O(m) 用於儲存鄰接表 e。優先佇列在最壞情況下可能儲存所有節點，因此空間複雜度也是 O(n)。

程式碼

#include <iostream>
#include <vector>
#include <queue>
using namespace std;
long long n,m,b,x,y,w,dp[100005];
vector <pair <long long,long long>> e[100005];
queue <pair <long long,long long>> q;//v dis
int main(){
	cin.tie(0); ios::sync_with_stdio(false);
	cin >> n >> m >> b;
	for(int i=0;i<n;++i){
		dp[i]=1e15;
	}
	for(int i=0;i<m;++i){
		cin >> x >> y >> w;
		e[x].push_back({y,w});
		e[y].push_back({x,w});
	}
	q.push({0,0});
	while(q.empty()==0){
		pair <long long,long long> tmp=q.front();
		q.pop();
		if(tmp.second>=dp[tmp.first])continue;
		dp[tmp.first]=tmp.second;
		for(int i=0;i<e[tmp.first].size();++i){
			q.push({e[tmp.first][i].first,tmp.second+e[tmp.first][i].second});
		}
	}
	cout << dp[b];
}