08-图8 How Long Does It Take (25分)（拓扑排序）

08-图8 How Long Does It Take (25分)
Given the relations of all the activities of a project, you are supposed to find the earliest completion time of the project.

Input Specification:
Each input file contains one test case. Each case starts with a line containing two positive integers N (≤100), the number of activity check points (hence it is assumed that the check points are numbered from 0 to N−1), and M, the number of activities. Then M lines follow, each gives the description of an activity. For the i-th activity, three non-negative numbers are given: S[i], E[i], and L[i], where S[i] is the index of the starting check point, E[i] of the ending check point, and L[i] the lasting time of the activity. The numbers in a line are separated by a space.

Output Specification:
For each test case, if the scheduling is possible, print in a line its earliest completion time; or simply output “Impossible”.

Sample Input 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

Sample Output 1:
18

Sample Input 2:
4 5
0 1 1
0 2 2
2 1 3
1 3 4
3 2 5

Sample Output 2:
Impossible

#include<iostream>
#include<queue>
using namespace std;
#define	max 10000
#define inf 65535
int n, m, a[max][max], ect;
int getmax(int arr[]) {
	int maxnum = 0;
	for (int i = 0; i < n; i++) 
		if (maxnum < arr[i])
			maxnum = arr[i];
	return maxnum;
}
int topsort()         //拓扑排序
{
	int v, cnt = 0, degreenum[max] = { 0 }, earliesttime[max] = { 0 };
	queue<int>q;
	for (int i = 0; i < n; i++) 
		for (int j = 0; j < n; j++) 
			if (a[i][j] != inf) 
				degreenum[j]++;
	for (int i = 0; i < n; i++) 
		if (degreenum[i] == 0)
			q.push(i);
	while (!q.empty()) {
		v = q.front();
		q.pop();
		cnt++;
		for (int i = 0; i < n; i++) {
			if (a[v][i] != inf) {
				if (earliesttime[v] + a[v][i] > earliesttime[i]) {      //比最大时间，工程前面的都结束后面才能开始
					earliesttime[i] = earliesttime[v] + a[v][i];
				}       //到每一个节点的最大时间中挑最大的
				if (--degreenum[i] == 0)
					q.push(i);
			}

			
		}
	}
	ect = getmax(earliesttime);
	if (cnt != n)return 0;
	else return 1;
}

int main() {
	int q, p;
	cin >> n >> m;
	//初始化图的边
	for (int i = 0; i < n; i++)
		for (int j = 0; j < n; j++)
			a[i][j] = inf;
	for (int i = 0; i < m; i++) {
		cin >> q >> p;
		cin>>a[q][p];
	}
	if (!topsort())
		cout << "Impossible" << endl;
	else
		cout << ect << endl;
	return 0;
}