洛谷P1807 最长路的三种做法

P1807 最长路https://www.luogu.com.cn/problem/P1807

下提供三种做法，分别为拓扑排序、SPFA、Floyd。详见注释，除了Floyd做法外其他均用邻接表+STL(vector)存图。可以比较它们的时间复杂度~~（我都开了氧气）~~

//45ms /  3.10MB /  892B C++14 (GCC 9) O2
#include 
using namespace std;
queueq;
int n,m;
int maxn[1510],mark[1510],ind[1510];
//maxn：到当前结点之前的最长路 
//mark:标记“在路径上”
//ind:记录每个结点的入度 
struct Edge
{
	int from;
	int to;
	int w;
}edge[50010];
vectorvec[50010];//vec为Edge型的，在已知起点时可直接通过这个调用出边权和终点 
void topo_sort()//拓扑排序 
{
	for (int i=1;i<=n;i++)
		if (ind[i]==0)
			q.push(i);//先将所有入度为0 的结点放入队列 
	while(q.size())
	{
		int now=q.front();//每次取出队首元素 
		q.pop();
		for(int j=0;j>n>>m;
	for(i=0;i 
 
SPFA
   
// 1:50ms /  3.21MB /  863B C++14 (GCC 9) O2
// 2:48ms /  3.13MB /  877B C++14 (GCC 9) O2
#include 
using namespace std;
queueq;
int n,m;
int maxn[1510],vis[1510];
//maxn：到当前结点之前的最长路 

struct Edge
{
	int from;
	int to;
	int w;
}edge[50010];
vectorvec[50010];//vec为Edge型的，在已知起点时可直接通过这个调用出边权和终点 

void SPFA1(int start)
{
	maxn[start]=0;
	q.push(start);
	while(q.size())
	{
		int now=q.front();//每次取出队首元素 
		q.pop();
		for(int j=0;j>n>>m;
	for(i=0;i 
 
Floyd 
//101ms /  4.34MB /  518B C++14 (GCC 9) O2
#include 
using namespace std;
int a[1510][1510];
int n,m;

int main()
{
	int i;
	cin>>n>>m;
	for(int i=1;i<=n;i++)
		for(int j=1;j<=n;j++)
			if(i==j) a[i][j]=0;
			else a[i][j]=-1;
	for(i=0;i 
					
										


					

						
欢迎分享，转载请注明来源：内存溢出
原文地址: http://outofmemory.cn/zaji/5713443.html