洛谷 P1807 最长路_NOI导刊2010提高(07)

2024-02-05 15:32

本文主要是介绍洛谷 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


题解

做法:拓扑排序+DAG上dp
这题还算是水题,拓扑排序去掉入度为1的点,然后就可以用bfs来做dp了,转移方程也很明显:
dj=max(dj,di+wi,j)(i,j)
关于这题为什么要拓扑排序,好像是不做拓扑排序就会在dp的时候出各种问题。。
下来贴代码:

#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<cstdlib>
#include<cmath>
#include<vector>
#include<queue>
using namespace std;
struct edge{int to,w;edge(int y,int l):to(y),w(l){}
};
int n,m;
vector<edge> G[1501];
int d[1501];
int du[1501];
void addedge(int x,int y,int l){G[x].push_back(edge(y,l));du[y]++;
}
void toposort(int s){queue<int> q;q.push(s);while(!q.empty()){int x=q.front();q.pop();for(int i=0;i<G[x].size();i++){edge &e=G[x][i];du[e.to]--;if(du[e.to]==0){q.push(e.to);}}G[x].clear();}
}
void bfs(int s){queue<int> q;q.push(s);while(!q.empty()){int x=q.front();q.pop();for(int i=0;i<G[x].size();i++){edge &e=G[x][i];if(d[x]+e.w>d[e.to]){d[e.to]=d[x]+e.w;q.push(e.to);}}}
}
int main(){scanf("%d%d",&n,&m);for(int i=1;i<=m;i++){int x,y,l;scanf("%d%d%d",&x,&y,&l);addedge(x,y,l);}for(int i=2;i<=n;i++){if(du[i]==0){toposort(i);}}if(du[n]==0){printf("-1");return 0;}bfs(1);printf("%d",d[n]);return 0;
}

这篇关于洛谷 P1807 最长路_NOI导刊2010提高(07)的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!



http://www.chinasem.cn/article/681358

相关文章

poj3261(可重复k次的最长子串)

题意:可重复k次的最长子串 解题思路:求所有区间[x,x+k-1]中的最小值的最大值。求sa时间复杂度Nlog(N),求最值时间复杂度N*N,但实际复杂度很低。题目数据也比较水,不然估计过不了。 代码入下: #include<iostream>#include<algorithm>#include<stdio.h>#include<math.h>#include<cstring

poj 3974 and hdu 3068 最长回文串的O(n)解法(Manacher算法)

求一段字符串中的最长回文串。 因为数据量比较大,用原来的O(n^2)会爆。 小白上的O(n^2)解法代码:TLE啦~ #include<stdio.h>#include<string.h>const int Maxn = 1000000;char s[Maxn];int main(){char e[] = {"END"};while(scanf("%s", s) != EO

键盘快捷键:提高工作效率与电脑操作的利器

键盘快捷键:提高工作效率与电脑操作的利器 在数字化时代,键盘快捷键成为了提高工作效率和优化电脑操作的重要工具。无论是日常办公、图像编辑、编程开发,还是游戏娱乐,掌握键盘快捷键都能带来极大的便利。本文将详细介绍键盘快捷键的概念、重要性、以及在不同应用场景中的具体应用。 什么是键盘快捷键? 键盘快捷键,也称为热键或快捷键,是指通过按下键盘上的一组键来完成特定命令或操作的方式。这些快捷键通常涉及同

hihocoder1050 : 树中的最长路

时间限制:10000ms 单点时限:1000ms 内存限制:256MB 描述 上回说到,小Ho得到了一棵二叉树玩具,这个玩具是由小球和木棍连接起来的,而在拆拼它的过程中,小Ho发现他不仅仅可以拼凑成一棵二叉树!还可以拼凑成一棵多叉树——好吧,其实就是更为平常的树而已。 但是不管怎么说,小Ho喜爱的玩具又升级换代了,于是他更加爱不释手(其实说起来小球和木棍有什么好玩的是吧= =)。小Ho手

POJ1631最长单调递增子序列

最长单调递增子序列 import java.io.BufferedReader;import java.io.InputStream;import java.io.InputStreamReader;import java.io.PrintWriter;import java.math.BigInteger;import java.util.StringTokenizer;publ

CSP 2023 提高级第一轮 CSP-S 2023初试题 完善程序第二题解析 未完

一、题目阅读 (最大值之和)给定整数序列 a0,⋯,an−1,求该序列所有非空连续子序列的最大值之和。上述参数满足 1≤n≤105 和 1≤ai≤108。 一个序列的非空连续子序列可以用两个下标 ll 和 rr(其中0≤l≤r<n0≤l≤r<n)表示,对应的序列为 al,al+1,⋯,ar​。两个非空连续子序列不同,当且仅当下标不同。 例如,当原序列为 [1,2,1,2] 时,要计算子序列 [

计蒜客 Skiing 最长路

In this winter holiday, Bob has a plan for skiing at the mountain resort. This ski resort has MM different ski paths and NN different flags situated at those turning points. The ii-th path from the

如何提高 GitHub 的下载速度

如何提高 GitHub 的下载速度 文章目录 如何提高 GitHub 的下载速度1. 注册账号2. 准备好链接3. 创建仓库4. 在码云上下载代码5. 仓库更新了怎么办 一般来说,国内的朋友从 GitHub 上面下载代码,速度最大是 20KB/s,这种龟速,谁能忍受呢? 本文介绍一种方法——利用“码云”,可以大大提高下载速度,亲测有效。 1. 注册账号 去“码云”注册一

PHP最长单一子串

<?php//方法一$s='abcccddddddcdefg';$max='';while($s!=''){$i=0; while($i<strlen($s) && $s[$i]==$s[0]) $i++;if ($i>strlen($max)){$max=substr($s,0,$i);} $s=substr($s,$i);}echo $m

day-50 求出最长好子序列 I

思路 二维dp,dp[i][h]表示nums[i] 结尾,且有不超过 h 个下标满足条件的最长好子序列的长度(0<=h<=k),二维数组dp初始值全为1 解题过程 状态转换方程: 1.nums[i]==nums[j],dp[i,h]=Math.max(dp[i,h],dp[j,h]+1) 2.nums[i]!=nums[j],dp[i,h]=Math.max(dp[i,h],dp[j,h-1