（拓扑排序；AOE图）
题目大意
给出一个工程各个活动的优先关系和所需时间，求完成这个工程所有活动的最短时间。如果无法完成，则输出Impossible。 题目链接
思路
拓扑排序。start为源点，ending为汇点。用一个变量num记录进入队列中的元素个数，如果不等于结点n，则表示不能完成（图中有环）。用数组ve表示事件的最早发生时间，则ve[ending]表示“所有活动已完成”这个事件的最早发生时间。对于每个结点v,用前驱结点u更新它的ve值：取ve[u]+uv边权的最大值。 题目中可能有多个起点和终点的情况。在拓扑排序之前进行判断，若起点或终点不唯一，则加入“超级源点”和“超级汇点”，即从超级源点出发，连接所有入度为0的点；从所有出度（G[i].size()）为0的点出发，连接超级汇点；添加的所有有向边的边权均为0。注意，在加入超级汇点时，要更新超级汇点的入度值，否则在判断是否存在拓扑序列时按照num是否==0来判断会出错。
AC代码
#define _CRT_SECURE_NO_WARNINGS
#include<cstdio>
#include<iostream>
#include<vector>
#include<queue>
using namespace std;
#define MAX 105
struct node {
int v, w;
};
vector<node>G[MAX];
int n, m, start, ending, in[MAX] = { 0 }, ve[MAX] = { 0 };
int topo() {
queue<int>q;
q.push(start);
int num = 0;
while (!q.empty()) {
int u = q.front();
q.pop();
num++;
for (int i = 0;i < G[u].size();i++) {
int v = G[u][i].v, w = G[u][i].w;
in[v]--;
if (in[v] == 0)q.push(v);
if (ve[v] < ve[u] + w)ve[v] = ve[u] + w;
}
}
if (num == n)return ve[ending];
else return -1;
}
int main() {
node temp;
scanf("%d%d", &n, &m);
for (int i = 0;i < m;i++) {
scanf("%d%d%d", &start, &temp.v, &temp.w);
G[start].push_back(temp);
in[temp.v]++;
}
int numin = 0, numout = 0;
for (int i = 0;i < n;i++) {
if (in[i] == 0) {
numin++;
start = i;
}
if (G[i].size() == 0) {
numout++;
ending = i;
}
}
if (numin > 1) {
start = n;temp.w = 0;
for (int i = 0;i < n;i++) {
if (in[i] == 0) {
temp.v = i;
G[start].push_back(temp);
in[i] = 1;
}
}
n++;
}
if (numout > 1) {
ending = n; in[ending] = numout;
temp.w = 0; temp.v = ending;
for (int i = 0;i < n;i++) {
if (G[i].size() == 0) {
G[i].push_back(temp);
}
}
n++;
}
int ans = topo();
if (ans == -1)printf("Impossible");
else printf("%d", ans);
return 0;
}
