P1807 最长路
题面
题目描述
设 为有 个顶点的带权有向无环图, 中各顶点的编号为 到 ,请设计算法,计算图 中 间的最长路径。
输入格式
输入的第一行有两个整数,分别代表图的点数 和边数 。
第 到第 行,每行 个整数 (),代表存在一条从 到 边权为 的边。
输出格式
输出一行一个整数,代表 到 的最长路。
若 无法到达 ,请输出 。
样例 #1
样例输入 #1
2 1
1 2 1
样例输出 #1
1
提示
【数据规模与约定】
- 对于 的数据,,。
- 对于 的数据,,。
- 对于 的数据,,,,。
思路
拓扑排序的同时进行一个 DP 就可以了。
我们定义为从号点到号点距离的最大值。
然后进行拓扑排序,能被1号点到达的点就打上标记并更新答案,因为可能也有入度为0的点但是不会被起点到达的点。
代码
#include<bits/stdc++.h>
using namespace std;
const int N=1699;
const int M=5e4+5;
int n,m,cnt;
int d[N],f[N];
int bj[N];//能被一号点到达的点才能更新答案
struct edge
{
int to,val,from;
};
vector<edge> e[1600];
void tpsort()
{
queue<int> Q;
for(int i=1;i<=n;i++)
if(d[i]==0)
Q.push(i);
while(!Q.empty())
{
int x=Q.front();
Q.pop();//枚举出边
for(int i=0,size=e[x].size();i<size;i++)//注意vector是从0开始
{
int p=e[x][i].to;
d[p]--;
if(bj[x]==1)
f[p]=max(f[p],f[x]+e[x][i].val),bj[p]=1;
if(!d[p]) Q.push(p);
}
}
return;
}
int main()
{
scanf("%d%d",&n,&m);
for(int i=1;i<=m;i++)
{
edge x;
scanf("%d%d%d",&x.from,&x.to,&x.val);
e[x.from].push_back(x);//以from开头的第i条边(的信息)存入
d[x.to]++;
}
memset(f,-1,sizeof(f));
bj[1]=1;
f[1]=0;//1~1距离为0
tpsort();
printf("%d",f[n]);
return 0;
}