Comment

RockyChen0205: 2023-12-15 12:11:43
AOE图的关键路径，代码如下：

#include<iostream>
#include<vector>
#include<queue>

using namespace std;
int main(){
	int T=0; //t行
	cin>>T;
	for(int t=0;t<T;t++){
		int n;
		cin>>n;
		vector<vector<int>> map(n,vector<int>(n,0));
		vector<int> count(n,0);  //拓扑排序过程中使用
		vector<int> ee(n,0);  //时间最早发生时间
		for(int i=0;i<n;i++){
			for(int j=0;j<n;j++){
				cin>>map[i][j];
				if(map[i][j]!=-1)
					count[j]++;  //数有j这个节点有多少个前驱结点
			}
		}
		queue<int> q;   
		vector<int> top;
		q.push(0);
		//拓扑排序
		while(!q.empty()){
			int p=q.front();
			q.pop();
			top.push_back(p);
			for(int i=0;i<n;i++){
				if(map[p][i]!=-1){
					count[i]--;
					if(count[i]==0) q.push(i);
				}
			}
		}
		
		for(auto t: top){
			int length=ee[t];  
			for(int i=0;i<n;i++){
				if(map[t][i]!=-1){
					int a=map[t][i];
					if(a+length>ee[i]){
						ee[i]=a+length;
					}
				}
			}
		}
		
		cout<<ee[n-1]<<endl;

	}
}