P1807 最长路_NOI导刊2010提高（07）
题目描述
设G为有n个顶点的有向无环图，G中各顶点的编号为1到n，且当为G中的一条边时有i < j。设w（i，j）为边的长度，请设计算法，计算图G中<1，n>间的最长路径。
输入格式
输入文件longest.in的第一行有两个整数n和m,表示有n个顶点和m条边，接下来m行中每行输入3个整数a，b，v（表示从a点到b点有条边，边的长度为v）。
输出格式
输出文件longest.out，一个整数，即1到n之间的最长路径.如果1到n之间没连通，输出-1。
输入输出样例
输入 #1
2 1
1 2 1
输出 #1
1
说明/提示
20%的数据，n≤100，m≤1000
40%的数据，n≤1,000，m≤10000
100%的数据，n≤1,500，m≤50000，最长路径不大于10^9
【思路】
拓扑排序 + DP
这道题和今天考试的第二题有点像
不过这道题必须要求的1到n这两个点之间的最长路
所以不能吧入度为0的点都放进去
而是应该只放进去1
对其他的入度为0但是不是1的点怎么处理呢？
枚举完1能到达的点并且减去入度之后
这些点不一定会为0
所以需要将那些多余的点删掉
这里的删掉指的是入度--
也就是把除了1以外的入度为0的点
进行拓扑排序
拓扑排序到的点就入度--
入度为0还是想像正常的拓扑一样放入栈/队列中去
直到栈/队列为空
然后再来一遍拓扑排序
只将1放入栈/队列中，
因为起点只能是1
在排序的过程中
可以进行DP
dp[i]表示i这个点到1的最长的距离
dp[i] = max(dp[i],dp[u] + w);
表示i这个点到1的最长距离等于max(它本身的值，他前一个点到1的最长距离+他和她前一个点之间的距离)
最后如果dp[n] == 0
也就是没有到达这个点
那就输出-1
否则输出dp[n]
【完整代码】
#include<iostream>
#include<cstdio>
#include<stack>
#define int long long
using namespace std;
const int Max = 50005;
struct node
{
int y,w,ne;
}a[Max];
int head[1505],sum = 0;
int into[1505];
void add(int u,int v,int w)
{
a[++ sum].y = v;
a[sum].ne = head[u];
a[sum].w = w;
head[u] = sum;
}
stack<int>s;
int dp[1505];
stack<int>q;
signed main()
{
int n,m;
cin >> n >> m;
int u,v,w;
for(register int i = 1;i <= m;++ i)
{
cin >> u >> v >> w;
add(u,v,w);
into[v] ++;
}
int jj = 0;
for(register int i = 1;i <= n;++ i)
if(into[i] == 0 && i != 1)
q.push(i);
while(!q.empty())
{
int u = q.top();
q.pop();
for(register int i = head[u];i != 0;i = a[i].ne)
{
into[a[i].y] --;
if(into[a[i].y] == 0)q.push(a[i].y);
}
}
s.push(1);
while(!s.empty())
{
int u = s.top();
s.pop();
for(register int i = head[u];i != 0;i = a[i].ne)
{
dp[a[i].y] = max(dp[a[i].y],dp[u] + a[i].w);
into[a[i].y] --;
if(into[a[i].y] == 0)s.push(a[i].y);
}
}
if(dp[n] == 0)cout << -1;
else cout << dp[n] << endl;
return 0;
}