P1807 最长路题解

题目

设G为有n个顶点的带权有向无环图，G中各顶点的编号为1到n，请设计算法，计算图G中1,n 间的最长路径。

输入输出格式

输入格式

输入的第一行有两个整数，分别代表图的点数n和边数m。

第2到第(m+1)行，每行3个整数u,v,w（u<v），代表存在一条从u到v边权为w的边。

输出格式

输出一行一个整数，代表1到n的最长路。

若1无法到达n，请输出−1。

输入输出样例

输入样例

2 1
1 2 1

输出样例

1

解析

题目中说（u<v），所以点1绝对是一个没有入度的点，而且不会出现环。这一点正好满足拓扑的要求。但是，题目并不保证只有点1是没有入度的。所以要判断其他没有入度的点。而对他们的处理是？也许你一开始会想到加入队列，那你就错了！他们本身是无法到达的点，所以根本不可能会延伸到其他地方，如果加入队列，那么就会导致个别点，甚至所有点的答案错误。那么就是不管他？还是错了！如果不管，那么他们延伸出来的点的入度永远大于0，因为还有那些点。以至于发生和上一种方法一样的错误，甚至使终点无法到达！那么解决方法就是先做一遍for循环，找到那些点，再把延伸出来的点的入度−1，如果这些点−1读入后又变成了入度为0的点，那么再做同样的处理。至于一个点的最长路的转移方程就是：

min{入度1+相应的边,入度2+相应的边……入度n加相应的边}

#include<iostream>
#include<vector>
#include<queue>
using namespace std;
int n,m,in[1505];//存入度数量 
vector<int>g[1505];//存边 
vector<int>d[1505];//存边权 
queue<int>q;
int v[1505];//存最长路 
int main(){
	cin>>n>>m;
	for(int i=1;i<=m;i++){
		int ff,tt,dd;
		cin>>ff>>tt>>dd;
		g[ff].push_back(tt);
		d[ff].push_back(dd);
		in[tt]++;
	}
	for(int i=2;i<=n;i++){
		v[i]=-1e9;
		if(!in[i]){
			q.push(i);
		}
	}//初始化 
	while(!q.empty()){
		int x=q.front();
		q.pop();
		for(int i=0;i<g[x].size();i++){
			if(!--in[g[x][i]]){
				q.push(g[x][i]);
			}
		}
	}//废除其他入度为0的点 
	q.push(1);
	while(!q.empty()){
		int x=q.front();
		q.pop();
		for(int i=0;i<g[x].size();i++){
			if(v[g[x][i]]<v[x]+d[x][i]){
				v[g[x][i]]=v[x]+d[x][i];
			}
			if(!--in[g[x][i]]){
				q.push(g[x][i]);
			}
		}
	}
	if(v[n]==-1e9){
		cout<<"-1";
	}
	else{
		cout<<v[n];
	}
	return 0;
}