首页 › 题库 › C/C++编程考级 › C/C++编程八级 › 简答题
简答题 偏难
#13196

最短工期 一个项目由若干个任务组成,任务之间有先后依赖顺序。项目经理需要设置一系列里程碑,在每个里程碑节点处检查任务的完成情况,并启动后续的任务。现给定一个项目…

最短工期

一个项目由若干个任务组成,任务之间有先后依赖顺序。项目经理需要设置一系列里程碑,在每个里程碑节点处检查任务的完成情况,并启动后续的任务。现给定一个项目中各个任务之间的关系,请你计算出这个项目的最早完工时间。

时间限制:1000

内存限制:65536

输入

首先第一行给出两个正整数:项目里程碑的数量 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

样例#2:

4 5
0 1 1
0 2 2
2 1 3
1 3 4
3 2 5

样例输出

样例#1:

18

样例#2:

Impossible
未登录也能判分,登录后才会记录
答案与解析
正确答案:<pre class="brush:cpp;toolbar:false">#include &lt;iostream&gt; #include &lt;vector&gt; #include &lt;queue&gt; using namespace std; int main() { int N, M; cin &gt;&gt; N &gt;&gt; M; vector&lt;vector&lt;pair&lt;int, int&gt;&gt;&gt; adj(N); vector&lt;int&gt; in_degree(N, 0); for (int i = 0; i &lt; M; ++i) { int u, v, d; cin &gt;&gt; u &gt;&gt; v &gt;&gt; d; adj[u].emplace_back(v, d); in_degree[v]++; } queue&lt;int&gt; q; vector&lt;int&gt; earliest_time(N, 0); for (int i = 0; i &lt; N; ++i) { if (in_degree[i] == 0) { q.push(i); } } int count = 0; while (!q.empty()) { int u = q.front(); q.pop(); count++; for (auto&amp; edge : adj[u]) { int v = edge.first; int d = edge.second; if (earliest_time[u] + d &gt; earliest_time[v]) { earliest_time[v] = earliest_time[u] + d; } in_degree[v]--; if (in_degree[v] == 0) { q.push(v); } } } if (count != N) { cout &lt;&lt; "Impossible" &lt;&lt; endl; } else { int max_time = 0; for (int t : earliest_time) { if (t &gt; max_time) { max_time = t; } } cout &lt;&lt; max_time &lt;&lt; endl; } return 0; }</pre>
这道题暂未补解析。