拓撲排序精講
卡碼網：117. 軟件構建(opens new window)
題目描述：
某個大型軟件項目的構建系統擁有 N 個文件，文件編號從 0 到 N - 1，在這些文件中，某些文件依賴于其他文件的內容，這意味著如果文件 A 依賴于文件 B，則必須在處理文件 A 之前處理文件 B （0 <= A, B <= N - 1）。請編寫一個算法，用于確定文件處理的順序。
輸入描述：
第一行輸入兩個正整數 N, M。表示 N 個文件之間擁有 M 條依賴關系。
后續 M 行，每行兩個正整數 S 和 T，表示 T 文件依賴于 S 文件。
輸出描述：
輸出共一行，如果能處理成功，則輸出文件順序，用空格隔開。
如果不能成功處理（相互依賴），則輸出 -1。
思路：
引入一個記錄每個節點的入度的數組，第i個位置存儲節點i的入度；
引入一個unordered_map記錄<int.vector<int>>記錄每個節點指向的節點；
引入結果數組，記錄安裝順序。
初始化
引入隊列queue，目的是存放當前找到的入度為0的節點；
遍歷節點，將入度為零的節點push進que
while循環（que中有節點）；
引入指針cur記錄隊首節點；pop隊首節點；把這個節點放入res數組；
引入files數組獲取cur節點對應unordered_map的配對數組；
遍歷files中的節點：入度--；如果該節點入度為零；該節點push到que中；
while結束
if(res中的節點數量==n）輸出結果
else 輸出-1；
#include <vector>
#include <iostream>
#include <queue>
#include <unordered_map>using namespace std;int main(){int n,m,s,t;cin>>n>>m;vector<int> inDgree(n,0);unordered_map<int,vector<int>> umap;vector<int> res;while(m--){cin>>s>>t;inDgree[t]++;umap[s].push_back(t);}//初始化queue<int> que;for(int i=0;i<n;i++){if(inDgree[i]==0) que.push(i);}while(que.size()){int cur=que.front();que.pop();res.push_back(cur);vector<int> files=umap[cur];if(files.size()){for(int i=0;i<files.size();i++){inDgree[files[i]]--;if(inDgree[files[i]]==0) que.push(files[i]);}}}if(res.size()==n){for(int i=0;i<n-1;i++) cout<<res[i]<<" ";cout<<res[n-1];}else cout<<-1<<endl;
}
dijkstra（樸素版）精講
卡碼網：47. 參加科學大會(opens new window)
【題目描述】
小明是一位科學家，他需要參加一場重要的國際科學大會，以展示自己的最新研究成果。
小明的起點是第一個車站，終點是最后一個車站。然而，途中的各個車站之間的道路狀況、交通擁堵程度以及可能的自然因素（如天氣變化）等不同，這些因素都會影響每條路徑的通行時間。
小明希望能選擇一條花費時間最少的路線，以確保他能夠盡快到達目的地。
【輸入描述】
第一行包含兩個正整數，第一個正整數 N 表示一共有 N 個公共汽車站，第二個正整數 M 表示有 M 條公路。
接下來為 M 行，每行包括三個整數，S、E 和 V，代表了從 S 車站可以單向直達 E 車站，并且需要花費 V 單位的時間。
【輸出描述】
輸出一個整數，代表小明從起點到終點所花費的最小時間。
思路
?dijkstra三部曲：
- 第一步，選源點到哪個節點近且該節點未被訪問過
- 第二步，該最近節點被標記訪問過
- 第三步，更新非訪問節點到源點的距離（即更新minDist數組）
在dijkstra算法中，minDist數組 用來記錄 每一個節點距離源點的最小距離。
minDist數組的含義：記錄所有節點到源點的最短路徑，應該初始為最大值。
代碼
首先處理輸入 初始化有向圖grid
設置起始節點終止節點
引入visited、minDist數組并初始化
1、找到距離起始節點最近且未被標記的節點
2、標記該節點被訪問過
3、更新minDist數組：這里需要遍歷節點，找到沒被訪問過且從cur->k節點存在路徑且minDist[cur]+grid[cur[k]<minDist[k]的節點才會用來更新minDist。
最后根據minDist[end]的值來輸出結果。
#include <iostream>
#include <vector>
#include <climits>
using namespace std;
int main(){int n,m,p1,p2,val;cin>>n>>m;vector<vector<int>> grid(n+1,vector<int>(n+1,INT_MAX));for(int i=0;i<m;i++){cin>>p1>>p2>>val;grid[p1][p2]=val;}//輸入處理，得到grid有權圖int start=1;int end=n;std::vector<int> minDist(n+1,INT_MAX);std::vector<bool> visited(n+1,false);minDist[start]=0;//初始化起始節點到自身距離為0for(int i=1;i<=n;i++){int minVal=INT_MAX;int cur=1;//1、選出距離源點最近的且未訪問的節點for(int j=1;j<=n;j++){if(!visited[j]&&minDist[j]<minVal){minVal=minDist[j];cur=j;}}//2、標記選出的節點已被訪問visited[cur]=true;//3、更新minDist數組for(int k=1;k<=n;k++){if(!visited[k]&&grid[cur][k]!=INT_MAX&&minDist[cur]+grid[cur][k]<minDist[k]){minDist[k]=minDist[cur]+grid[cur][k];}}}if(minDist[end]==INT_MAX) cout<<-1<<endl;else cout<<minDist[end]<<endl;
}
