题目选自洛谷P1807

对于一个有向无环图，可以采取广搜将结点依次搜索，记录当前结点的最长路并在循环过程中不断更新。

题目描述

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

输入格式

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

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

输出格式

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

若 1 与 n 不连通，请输出 −1。

输入输出样例

输入 1

2 1
1 2 1

输出 1

1

解题代码： 

#include<stdio.h>
#include<iostream>
#include<math.h>
#include<algorithm>
#include<queue>
using namespace std;
queue<int>q;
int n,m,u,v,w;
int d[1501],mp[1501][1501];
void bfs(){
	memset(d,-1,sizeof(d));
	d[1]=0; q.push(1); //初始化操作
	while(!q.empty()){
		int t = q.front();
		for(int i=1;i<=n;i++){
			if(mp[t][i] && d[i] < d[t] + mp[t][i]){
			//如果从队列头到当前结点i有边，但不是最长
			//（即此点的最长路小于队列头最长路加t-i的路径长） 
				d[i] = d[t] + mp[t][i];
				q.push(i);
			}
		}
		q.pop();
	}
}
int main(){
	cin>>n>>m;
	for(int i=0;i<m;i++){
		cin>>u>>v>>w;
		mp[u][v]=max(mp[u][v],w);
	}
	bfs();
	cout<<d[n];
	return 0;
}