luogu 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。

拓扑排序求最长路

#include<iostream>

#include<cstdio>

#include<queue>

using namespace std;

const int N=1e3+5e2+11,M=5e4+10;

int in[N],maxn[M],bj[M];

int Next[M],head[N],go[M],w[M],tot;

inline void add(int u,int v,int o){

	Next[++tot]=head[u];head[u]=tot;go[tot]=v;w[tot]=o;

}

int n,m;

void TopSort()

{

	queue<int>q;

	for(int i=1;i<=n;i++)

	if(in[i]==0)q.push(i);

	while(q.size()){

		int u=q.front();

		q.pop();

		for(int i=head[u];i;i=Next[i]){

			int y=go[i];

			in[y]--;

			if(bj[u]==1){

				if(maxn[y]<maxn[u]+w[i])

				maxn[y]=maxn[u]+w[i];

				bj[y]=1;

			}

			if(in[y]==0)q.push(y);

		}

	}

}

int main(){

	cin>>n>>m;

	for(int i=1,u,v,o;i<=m;i++){

		scanf("%d%d%d",&u,&v,&o);

		add(u,v,o);in[v]++;

	}

	maxn[n]=-1;bj[1]=1;

	TopSort();

	cout<<maxn[n]<<endl;

	return 0;

}

spfa求最长路

#include<queue>

#include<cstdio>

#include<cstring>

#include<iostream>

#include<algorithm>

using namespace std;

const int N=2510,M=5e5+10,inf=1<<30;

int nxt[M],head[N],go[M],w[M],tot;

inline void add(int u,int v,int o){

	nxt[++tot]=head[u];head[u]=tot;go[tot]=v;w[tot]=o;

}

int n,m,dis[N];

bool vis[N];

queue<int>q;

inline void dj(){

	memset(dis,0xcf,sizeof(dis)); q.push(1); dis[1]=0;

	while(q.size()){

		int u=q.front(); vis[u]=0; q.pop();

		for(int i=head[u];i;i=nxt[i]){

			int v=go[i];

			if(dis[v]<dis[u]+w[i]){

				dis[v]=dis[u]+w[i];

				if(!vis[v])q.push(v),vis[v]=1;

			}

		}

	}

}

signed main(){

	cin>>n>>m;

	for(int i=1,u,v,o;i<=m;i++){

		scanf("%d%d%d",&u,&v,&o);

		add(u,v,o);

	}

	dj();

	if(dis[n]>=0)cout<<dis[n]<<endl;

	else cout<<-1<<endl;

}

巴特西

luogu P1807 最长路_NOI导刊2010提高（07）

题目描述

输入格式

输出格式

最新文章

热门文章