18747 最长路径

分手后的思念是犯贱 2023-02-17 02:48 7阅读 0赞

时间限制:1000MS 代码长度限制:10KB  
提交次数:0 通过次数:0

题型: 编程题 语言: 不限定  
Description  
在一个工程项目里，多项工作可以同时进行。  
我们可以用有向无环图表述项目流程，把项目中的事件表述为结点，把活动表述成有权值的边。  
现在我们已知项目共有n个事件，起点为1，终点为n，m个活动。  
请你计算出这个项目的最早完成事件，也就是起点到收点的最长路径。

输入格式  
第一行两个整数n和m，代表结点数量和边数量。(1<=n,m<=100)  
下面m行，每行3个整数a,b,x,表示点a到点b之间有一条长度为x的有向边。

输出格式  
一个整数，起点到终点的最长路径.

输入样例  
4 6  
1 2 3  
1 3 2  
1 4 3  
2 3 3  
2 4 5  
3 4 3

输出样例  
9

作者 30002692

解题思路：利用拓扑排序可以得到最长路径长度，同时可以利用path数组记录最长路径。

#include<iostream>
    #include<algorithm>
    #include<cmath>
    #include<cstring>
    #include<vector> 
    #include<queue>
    using namespace std;
    typedef long long ll;
    int d[105],t[105],path[105];//d记录该顶点的入度，t记录该顶点的代表的事件的最早发生时间，path记录当前点最长路径的前驱结点的下标 
    struct node 
    { 
    	int adj,value;
    };
    vector<node> e[105];
    void print(int x)
    { 
    	if(x==1)
    	{ 
    		cout<<x<<' ';
    		return ;
    	}
    	print(path[x]);
    	cout<<x<<' ';
    }
    int main()
    { 
       ios::sync_with_stdio(false);
       int n,m,i,x,y,z; 
       cin>>n>>m;
       for(i=1;i<=m;i++)
       { 
       	cin>>x>>y>>z;
       	e[x].push_back({ y,z});
       	d[y]++;//统计入度 
       }
       queue<int> q;
       q.push(1);
       while(!q.empty())
       { 
       	int temp=q.front();
       	q.pop();
       	for(i=0;i<e[temp].size();i++)
       	{ 
       		int ad=e[temp][i].adj;
       		int val=e[temp][i].value;
       		d[ad]--;//相应点入度减一 
       		if(d[ad]==0)//入队 
       		q.push(ad);
       		if(t[ad]<t[temp]+val)//比较得出最长路径（动态规划）
       		{ 
       			t[ad]=t[temp]+val;
       			path[ad]=temp;//记录当前最长路径的前驱 
    		}	    
    	}
       }
       cout<<t[n]<<endl;
       print(n);
       return 0;
    }