知识点

Dijkstra算法不能求最长路径 ，常使用SPFA

经典Dijkstra算法根据贪心思想，每次通过所在的点路径最短的路径来松弛其他点，并且保证了这个操作每个点只会进行一次（除了距离最远的点，因为最后一点被松弛完整个算法就结束了），但是，求最长路径的时候不能保证在当前所经过的路径最长，最后的总长也最长，即最优子结构无法满足整体最优 。

这时候就需要使用动态规划了，而SPFA算法就是基于动态规划而形成的算法

---

 例题：洛谷 P1807 最长路

题目描述

设 G 为有 n 个顶点的带权有向无环图，G 中各顶点的编号为 1 到 n，请设计算法，计算图 G 中 1, n 间的最长路径。

输入格式

输入的第一行有两个整数，分别代表图的点数 n 和边数 m。

第 2 到第 (m + 1) 行，每行 33 个整数 u,v,w（u

输出格式

输出一行一个整数，代表 1 到 n 的最长路。

若 1 与 n 不连通，请输出 −1。

输入输出样例

输入 #1

2 1
1 2 1

输出 #1

1

说明/提示

【数据规模与约定】

• 对于 20%的数据，n≤100，m≤10^3。
• 对于 40% 的数据，n≤10^3，m≤10^4。
• 对于 100% 的数据，1≤n≤1500，1≤m≤5×10^4，1≤u,v≤n，-10^5 ≤w≤10^5。

---

 ① 使用经典Dijkstra算法 （56pts）

#include 
#include 
#include 
#include 
#include 
#include 
using namespace std;
int n,m;
const int maxn=1e7+5;
struct node
{
	int to,next,w;
}edge[maxn<<1];
int head[maxn],dis[maxn],ans[maxn],num=0;
bool vis[maxn];
struct node1{
	int ans,id;
	bool operator <(const node1&x) const
	{
		return x.ans > ans;
	}
};
priority_queue  q;
inline int read()
{
	int x=0,f=1;
	char c=getchar();
	while(c<'0'||c>'9')
	{
		if(c=='-') f=-1;
		c=getchar();
	}
	while(c>='0'&&c<='9')
	{
		x=(x<<3)+(x<<1)+(c^48);
		c=getchar();
	}
	return x*f;
}
 
inline void write(int x)
{
	if(x<0) putchar('-'),x=-x;
	if(x>9) write(x/10);
	putchar(x%10+'0');
}
 
inline void add(int u,int v,int w)
{
	edge[++num].to=v;
	edge[num].w=w;
	edge[num].next=head[u];
	head[u]=num;
}
 
inline void dij()
{
	int u;
	dis[1]=0;
	q.push((node1){0,1});
	while(!q.empty())
	{
		node1 temp=q.top();
		u=temp.id;
		q.pop();
		if(vis[u]) continue;
		vis[u]=true;
		for(int i=head[u];i!=-1;i=edge[i].next)
		{
			int v=edge[i].to;
			if(dis[v]//将大于号改为小于号
			{
				dis[v]=dis[u]+edge[i].w;
				if(!vis[v]) q.push((node1){dis[v],v});
			}
		}
	}
	
}
 
int main()
{
	n=read(); m=read();
	memset(head,-1,sizeof(head));
	memset(dis,-1,sizeof(dis)); //dis[]设为-1，相当于平日MAX=-999999999
	for(int i=1;i<=m;++i)
	{
		int u=read(),v=read(),w=read();
		add(u,v,w);
	}
	dij();
	write(dis[n]);
	return 0;
}

 ②  已AC代码：（只去掉了vis[ ] 的判断）

#include 
#include 
#include 
#include 
#include 
#include 
using namespace std;
int n,m;
const int maxn=1e7+5;
struct node
{
	int to,next,w;
}edge[maxn<<1];
int head[maxn],dis[maxn],num=0;
bool vis[maxn];
struct node1{
	int ans,id;
	bool operator <(const node1&x) const
	{
		return x.ans > ans;
	}
};
priority_queue  q;
inline int read()
{
	int x=0,f=1;
	char c=getchar();
	while(c<'0'||c>'9')
	{
		if(c=='-') f=-1;
		c=getchar();
	}
	while(c>='0'&&c<='9')
	{
		x=(x<<3)+(x<<1)+(c^48);
		c=getchar();
	}
	return x*f;
}
 
inline void write(int x)
{
	if(x<0) putchar('-'),x=-x;
	if(x>9) write(x/10);
	putchar(x%10+'0');
}
 
inline void add(int u,int v,int w)
{
	edge[++num].to=v;
	edge[num].w=w;
	edge[num].next=head[u];
	head[u]=num;
}
 
inline void dij()
{
	int u;
	dis[1]=0;
	q.push((node1){0,1});
	while(!q.empty())
	{
		node1 temp=q.top();
		u=temp.id;
		q.pop();
		//去掉了vis[]的判断
		for(int i=head[u];i!=-1;i=edge[i].next)
		{
			int v=edge[i].to;
			if(dis[v]
			{
				dis[v]=dis[u]+edge[i].w;
				q.push((node1){dis[v],v});
			}
		}
	}
	
}
 
int main()
{
	n=read(); m=read();
	memset(head,-1,sizeof(head));
	memset(dis,-1,sizeof(dis));
	for(int i=1;i<=m;++i)
	{
		int u=read(),v=read(),w=read();
		add(u,v,w);
	}
	dij();
	write(dis[n]);
	return 0;
}