立志用最少的代碼做最高效的表達

---

一個項目由若干個任務組成，任務之間有先后依賴順序。項目經理需要設置一系列里程碑，在每個里程碑節點處檢查任務的完成情況，并啟動后續的任務。現給定一個項目中各個任務之間的關系，請你計算出這個項目的最早完工時間。

輸入格式：
首先第一行給出兩個正整數：項目里程碑的數量 N（≤100）和任務總數 M。這里的里程碑從 0 到 N?1 編號。隨后 M 行，每行給出一項任務的描述，格式為“任務起始里程碑 任務結束里程碑 工作時長”，三個數字均為非負整數，以空格分隔。

輸出格式：
如果整個項目的安排是合理可行的，在一行中輸出最早完工時間；否則輸出"Impossible"。

輸入樣例 1：
9 12
0 1 6
0 2 4
0 3 5
1 4 1
2 4 1
3 5 2
5 4 0
4 6 9
4 7 7
5 7 4
6 8 2
7 8 4
輸出樣例 1：
18

輸入樣例 2：
4 5
0 1 1
0 2 2
2 1 3
1 3 4
3 2 5
輸出樣例 2：
Impossible

---

拓撲排序模板題。（其實用dfs硬搜也能解出來-，-）

步驟：
1、定義隊列，存入起始活動（不止一個）
2、對每個活動指向的活動進行遍歷，同時更新每個活動的最早完成時間。
3、若遍歷的點等于n，則證明成功，輸出最終活動的最早完成時間；反之輸出Impossible

---

#include<iostream> #include<cstdio> #include<vector> #include<queue> /* 拓撲排序， 隊列存儲、實時更新最短路徑。 */ using namespace std; const int N = 105; vector<pair<int, int> >G[N]; //第i個節點到到某個節點+到該節點花費的時間 int n, m; int in[N]; //存儲所有節點的入度數 int ans[N]; int dis[N]; //存儲完成某活動所需的最短時間 int tot = 0; //記錄已遍歷的節點 int main() {cin >> n >> m;for(int i = 0, u, v, w; i < m; i++) {cin >> u >> v >> w;in[v]++; //v節點出度+1 G[u].push_back({v, w});}queue<int>Q;for(int i = 0; i < n; i++) if(!in[i]) Q.push(i); //入度為0的，都是起點while(!Q.empty()) {int u = Q.front();Q.pop(), ans[tot++] = u;for(auto x : G[u]) {int v = x.first, w = x.second;if(--in[v] == 0) //因為一個點不能重復入隊，因此等度數減為0(其前序的節點都遍歷完)時再入度。 Q.push(v);if(dis[v] < dis[u] + w)dis[v] = dis[u] + w;}}if(tot == n) { //如果計數節點等于n，代表成功 int ans1 = 0;for(int i = 0; i < n; i++) //找最大值 ans1 = max(ans1, dis[i]);cout << ans1 << '\n'; } else cout << "Impossible";return 0; }

---

耗時

---

????????——弱小和無知不是生存的障礙，傲慢才是。

總結

以上是生活随笔為你收集整理的最短工期 (25 分)【拓扑排序模板】的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。