首页 > 代码库 > P1807 最长路_NOI导刊2010提高（07）
P1807 最长路_NOI导刊2010提高（07）
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 11 2 1
输出样例#1：
1
说明
20%的数据，n≤100，m≤1000
40%的数据，n≤1,000，m≤10000
100%的数据，n≤1,500，m≤50000，最长路径不大于10^9
spfa最长路
1 #include<cstdio> 2 #include<algorithm> 3 #include<cstring> 4 #include<queue> 5 using namespace std; 6 const int MAXN = 1510; 7 8 struct Edge{ 9 int to,w,nxt;10 }e[50100];11 12 int dis[MAXN];13 int head[MAXN];14 bool vis[MAXN];15 queue<int>q;16 int n,m,cnt;17 18 void add(int u,int v,int w) //从u到v有一条长度是w的边 19 {20 ++cnt;21 e[cnt].to = v;22 e[cnt].w = w;23 e[cnt].nxt = head[u];24 head[u] = cnt;25 }26 27 void spfa()28 {29 for (int i=1; i<=n; ++i) dis[i] = -1;30 dis[1] = 0;31 q.push(1);32 vis[1] = true;33 while (!q.empty())34 {35 int u = q.front();36 q.pop();37 for (int i=head[u]; i; i=e[i].nxt)38 {39 int v = e[i].to;40 int w = e[i].w;41 if (dis[v]<dis[u]+w)42 {43 dis[v] = dis[u]+w;44 if (!vis[v])45 {46 q.push(v);47 vis[v] = true;48 }49 }50 }51 vis[u] = false;52 }53 }54 55 int main()56 {57 scanf("%d%d",&n,&m);58 for (int u,v,w,i=1; i<=m; ++i)59 {60 scanf("%d%d%d",&u,&v,&w);61 add(u,v,w); 62 }63 spfa();64 printf("%d",dis[n]);65 return 0;66 }
P1807 最长路_NOI导刊2010提高（07）
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。