3043: 【普及/提高-】【P1807】最长路

【数据规模与约定】

• 对于 的数据，，。
• 对于  的数据，，。
• 对于  的数据，，，，。

#include <bits/stdc++.h>

using namespace std;
//拓扑排序+vector实现
const int N = 50000 + 10;
const int INF = 0x3f3f3f3f;

//结构体
struct Edge {
    int to;    //下一个结点
    int value; //边长
    int next;  //索引值
};
vector<Edge> p[N];

int ind[N]; //入度
int f[N];   //动态规划的结果
queue<int> q;   //拓扑排序用的队列
int n; //n个顶点
int m; //m条边

int main() {
    //读入
    cin >> n >> m;
    for (int i = 1; i <= m; ++i) {
        int u, v, w;//代表存在一条从 u 到 v 边权为 w 的边。
        cin >> u >> v >> w;
        p[ u ].push_back({v, w});
        ind[v]++;//统计入度个数
    }
    //入度为0的结点入队列，进行拓扑排序
    for (int i = 1; i <= n; i++) if (!ind[i]) q.push(i);

    //初始化,将到达节点1的距离设为最大值,这个用的太妙了~~
    //防止出现负权边，也防止出现了0不知道是权边加在一起出现的，还是天生就是0
    //调高起点值看来是解决负权边的重要方法，学习学习。
    f[1] = INF;

    //拓扑排序
    while (!q.empty()) {
        int u = q.front();
        q.pop();
        //遍历每条出边
        for (int i = 0; i < p[ u ].size(); i++) {
            int y = p[ u ][i].to;
            --ind[y]; //在删除掉当前结点带来的入度
            //精髓！~
            //运用拓扑排序的思想,对每个节点进行访问,并在此处用上动态规划的思路更新到此节点的最大距离
            f[y] = max(f[y], f[ u ] + p[ u ][i].value); //利用走台阶思路，从上一级走过来
            if (!ind[y]) q.push(y);//在删除掉当前结点带来的入度后，是不是入度为0了，如果是将点y入队列
        }
    }
    //如果可以到达，则输出最长路径
    if (f[n] > 0)printf("%d", f[n] - INF);
    else printf("-1");
    return 0;
}

#include<bits/stdc++.h>
using namespace std;
#define MAXN 1510
#define MAXM 50010
const int INF = 0x3f3f3f3f;
int n,m;
int f[MAXN],ind[MAXN],b[MAXN];
struct edge {
	int v,w;
};
vector <edge> p[MAXN];
queue <int> q; 
int main(){
    cin >> n >> m;
    for (int i = 0; i < m; i++) {
    	int u,v,w;
    	cin >>u>>v>>w;
		p[ u ].push_back( (edge) { v, w } );
    	ind[v]++;
	}
	f[1] = INF;
	b[1]=1;
	for (int i = 1; i <= n; i++)
	    if (ind[i] == 0)
		    q.push(i);
	while (!q.empty()) {
		int x = q.front();
		q.pop();
		for (int i = 0, sz = p[x].size(); i < sz; i++) {
			if (b[x] == 1) {
				if (f[x] + p[x][i].w > f[p[x][i].v] ) f[p[x][i].v] = f[x] + p[x][i].w;
				b[p[x][i].v] = 1;
			}
			ind[p[x][i].v]--;
			if (ind[p[x][i].v] == 0) {	
				q.push(p[x][i].v);
			} 
		}
	}
	if (f[n]>0) cout<<f[n]-INF;
    else cout <<"-1";
	return 0;
}