ftp网站备份,wordpress恢复默认,安亭公司网站建设,想建个企业网站最长路
题目描述
设 G G G 为有 n n n 个顶点的带权有向无环图#xff0c; G G G 中各顶点的编号为 1 1 1 到 n n n#xff0c;请设计算法#xff0c;计算图 G G G 中 1 , n 1, n 1,n 间的最长路径。
输入格式
输入的第一行有两个整数#xff0c;分别代表图的点数…最长路
题目描述
设 G G G 为有 n n n 个顶点的带权有向无环图 G G G 中各顶点的编号为 1 1 1 到 n n n请设计算法计算图 G G G 中 1 , n 1, n 1,n 间的最长路径。
输入格式
输入的第一行有两个整数分别代表图的点数 n n n 和边数 m m m。
第 2 2 2 到第 ( m 1 ) (m 1) (m1) 行每行 3 3 3 个整数 u , v , w u, v, w u,v,w u v uv uv代表存在一条从 u u u 到 v v v 边权为 w w w 的边。
输出格式
输出一行一个整数代表 1 1 1 到 n n n 的最长路。
若 1 1 1 无法到达 n n n请输出 − 1 -1 −1。
样例 #1
样例输入 #1
2 1
1 2 1样例输出 #1
1提示
【数据规模与约定】
对于 20 % 20\% 20%的数据 n ≤ 100 n \leq 100 n≤100 m ≤ 1 0 3 m \leq 10^3 m≤103。对于 40 % 40\% 40% 的数据 n ≤ 1 0 3 n \leq 10^3 n≤103 m ≤ 1 0 4 m \leq 10^{4} m≤104。对于 100 % 100\% 100% 的数据 1 ≤ n ≤ 1500 1 \leq n \leq 1500 1≤n≤1500 0 ≤ m ≤ 5 × 1 0 4 0 \leq m \leq 5 \times 10^4 0≤m≤5×104 1 ≤ u , v ≤ n 1 \leq u, v \leq n 1≤u,v≤n − 1 0 5 ≤ w ≤ 1 0 5 -10^5 \leq w \leq 10^5 −105≤w≤105。
#includebits/stdc.h
using namespace std;
#define il inline
const int MAXN5e55;
int dis[MAXN],w[MAXN],n,m,minn,f[MAXN][3];//Bellman-Ford
il void BellmanFord()
{memset(dis,0x3f,sizeof(dis));dis[1]0;for(int i1;in-1;i)for(int j1;jm;j)dis[f[j][2]]min(dis[f[j][2]],dis[f[j][1]]w[j]);return;
}
//int main()
{cinnm;for(int i1;im;i)f[i][1]f[i][2]0;memset(w,0x3f,sizeof(w));for(int i1;im;i){int u,v,ww;cinuvww;f[i][1]u,f[i][2]v,w[i]-ww;}BellmanFord();if(dis[n]!0) printf(%d,-dis[n]);else printf(-1);return 0;
}
