洛谷P1807 最长路（拓扑排序）

题目链接：P1807 最长路 - 洛谷 | 计算机科学教育新生态

题目描述

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

输入格式

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

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

输出格式

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

若 1 无法到达 n，请输出 −1。

输入输出样例

输入 #1复制

2 1
1 2 1

输出 #1

1

说明/提示

【数据规模与约定】

• 对于 20%，n≤100n≤100
• 对于 40%的数据，n≤103n≤103。
• 对于 100%的数据，1≤n≤1500，0≤m≤5×104，1≤u,v≤n，−105≤w≤105。

解题思路：本题也用到了图论中的拓扑排序，与以往不同本题要求求1 ~ n的路径长度，所以要先将1这个点加入队列，然后从节点1开始不断遍历更新距离。

代码部分：

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;

const int N = 1e5 + 10,INF = -1e9;; 

int n,m;
int h[N],e[N],ne[N],w[N],idx;//邻接表存图 
int q[N],dis[N]; 
int in[N];//in表示入度                           

void add(int a,int b,int c)//建立一条从a指向b的边,权值为c 
{
    e[idx] = b,ne[idx] = h[a],w[idx] = c,h[a] = idx++;
}

void topsort()//拓扑排序 
{
	int hh = 0,tt = -1;
	
	q[++tt] = 1;
	dis[1] = 0;
	for(int i = 2; i <= n; i++)//将度数为0的点插入队列 
    {
    	dis[i] = INF;
    	if(!in[i]) {//初始化方案数
    		q[++tt] = i;
		} 
	}
	
	while(hh <= tt)
	{
		int t = q[hh++];//取出队头         
		
		for(int i = h[t]; i != -1; i = ne[i])//遍历所有边 
		{
			int j = e[i];//取出能到达的点 
			in[j]--;// 处理与当前节点相关的邻接节点的入度
			dis[j] = max(dis[j],dis[t] + w[i]);
			if(!in[j]) q[++tt] = j;// 如果入度为0，将其加入队列
		}
	}
	
}

int read()
{
    int t = 0, f = 1;
    char ch = getchar();
    while(ch > '9' || ch < '0') {
        if(ch == '-') f = -1;
        ch = getchar();
    }
    while(ch <= '9' && ch >= '0') {
        t = t * 10 + ch - '0';
        ch = getchar();
    }
    return t * f;
} 

int main() 
{
    n = read(),m = read();
    
    memset(h, -1, sizeof(h));//一定要初始化 
    
    
    while(m--)
    {
    	int u = read(),v = read(),w = read();
    	in[v]++;
    	add(u,v,w);
	}
	
	topsort();

	if(dis[n] != INF) cout<<dis[n];
	else cout<<-1;
	
    
    return 0;
}