2024華為OD機試題庫-(C卷+D卷)-(JAVA、Python、C++)
題目描述
一個局域網內有很多臺電腦，分別標注為 0 ~ N-1 的數字。相連接的電腦距離不一樣，所以感染時間不一樣，感染時間用 t 表示。
其中網絡內一臺電腦被病毒感染，求其感染網絡內所有的電腦最少需要多長時間。如果最后有電腦不會感染，則返回-1。
給定一個數組 times 表示一臺電腦把相鄰電腦感染所用的時間。
如圖：path[i] = {i, j, t} 表示：電腦 i->j，電腦 i 上的病毒感染 j，需要時間 t。
輸入描述
4
3
2 1 1
2 3 1
3 4 1
2
輸出描述
2
用例1
輸入
4
3
2 1 1
2 3 1
3 4 1
2
輸出
2
說明
第一個參數：局域網內電腦個數N，1 ≤ N ≤ 200；
第二個參數：總共多少條網絡連接
第三個 2 1 1 表示2->1時間為1
第六行：表示病毒最開始所在電腦號2
考點
dijkstra算法
解題思路
本題是dijkstra算法的題目，可以參考【華為OD機試c++】最長廣播效應【2023 B卷|200分】_最長廣播效應 od-CSDN博客的解題思路。
代碼
c++
#include <bits/stdc++.h>
using namespace std;int main() {int n,m;//n電腦個數，m連接數cin>>n>>m;int hi=10000000;vector<vector<int>> mat(n+1,vector<int>(n+1,hi)); //創建鄰近矩陣for(int i=0;i<m;i++) {int a,b,t;cin>>a>>b>>t;mat[a][b]=t;}
)
