P1807 最长路

题目原文及输入/输出格式

题目描述

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

拓扑排序解法

因为是有向无环图DAG，所以可以用拓扑排序计算路径。

因为是要计算<1,n>的最长路，所以要引入一个bj数组，只更新1号点能够到达的点的路径长度。

#include<cstdio>
#include<cmath>
#include<cstring>
#include<iostream>
#include<vector>
#include<stack> 
#include<algorithm>
#include<map>
#include<queue>
#include<stack>
#include<climits>
using namespace std;

struct edge{
	int to, weight;
	
	edge(int t, int w){
		this->to=t;
		this->weight=w;
	}
}; 

vector<edge> G[50010]; //邻接表存图
int n, m, ans[1510], inDeg[1510], bj[1510];
queue<int> Q;

int main(){
	cin>>n>>m;
	for(int i=1;i<=m;i++){
		int a, b, c;
		cin>>a>>b>>c;
		inDeg[b]++; //计算入度
		G[a].push_back(edge(b, c));
	}
	
	for(int i=1;i<=n;i++){
		if(inDeg[i]==0) Q.push(i); //将入度为0的点插入队列
	}
	
	bj[1]=1; //标记1号点
	while(!Q.empty()){
		int f=Q.front();
		
		for(int i=0;i<G[f].size();i++){
			edge e=G[f][i];
			inDeg[e.to]--;
			if(bj[f]==1){ //只有起点是1号点或者是1号点能到的点才更新数据
				ans[e.to]=max(ans[e.to], ans[f]+e.weight); //更新数据
				bj[e.to]=1; //把这个点也标记成1号点能到的点
			}
			if(inDeg[e.to]==0){ //入度被减为0，插入队列
				Q.push(e.to);
			}
		}
		
		Q.pop();
	}
	
	int aaa=ans[n]; //计算答案
	if(aaa!=0) cout<<aaa;
	else cout<<-1;
	return 0;
}

更多解法

to be continued…