最短路的求法，有很多，Floyd、Dijkstra、Bellma-Ford，但是我们来思考一下最长路，SPFA和Floyd必然可以跑最长路，一个是DP，一个是基于更新的更新，所以由于这两种特性，决定了他们能够跑最长路，但是最不会被卡的Dijkstra在这里就显得蹩脚了。
为什么？我们来看一下这种情况：
最长路更新的话，最先出队的是1-4边，但是她不能更松弛别人，此时1-4边=3
然后1-3出队，他能松弛1-4 此时1-3为2 1-4为5
然后1-2出队，他能松弛1-3 此时1-2为1 1-3 为3
但是3不能再入队松弛别人了。
所以导致了答案错误。
想一下
为什么能跑最短路，因为路径长度不减，这是算法的核心，而到了最长路，理应是路径长度不增，但是我们看到我们确定边的过程为 3 2 5 1 3不满足单调性，所以必然错误。
这是时候有人就要说了，那我们为什么不去掉vis数组呢，那么算法就要退化，复杂度变成了什么？最坏这不就成了bfs了吗???
我在这里提出一种优化，但是仅限于路径长度较短的情况下，Node中多加一个double类型的数据记录长度分之一，用来跑最短路，但是由于精度的限制1e6数据就开始发飘。
//dijkstra 去掉VIS数组
#include<bits/stdc++.h>
using namespace std;
const int INF=0x3f3f3f3f;
typedef long long ll;
typedef pair<int,int> PII;
struct Node
{
int var,next,val;
} edge[100000005];
int head[100005],tot,dis[100005],N,M;
bool vis[100005];
priority_queue<PII> Q;
void add(int a, int b, int c)
{
edge[++tot].var = b;
edge[tot].val = c;
edge[tot].next = head[a];
head[a] = tot;
}
void init()//多组输入调用
{
tot=0;
memset(head,0,sizeof(head));
}
void dijkstra(int s)
{
for(int i=0;i<=N;i++)dis[i]=-INF;
//memset(vis,0,sizeof(vis));
//while(Q.size()) Q.pop();
dis[s] = 0;
Q.push(make_pair(0,s));
while(!Q.empty())
{
int x=Q.top().second;
Q.pop();
if(vis[x])continue;
//vis[x]=1;
for(int i=head[x]; i; i=edge[i].next)
{
int y=edge[i].var;
if(dis[x]+edge[i].val>dis[y])
{
dis[y]=dis[x]+edge[i].val;
//if(!vis[y])
Q.push(make_pair(dis[y],y));
}
}
}
}
int main()
{
int S;
scanf("%d %d",&N,&M);
while(M--)
{
int x,y,z;
scanf("%d %d %d",&x,&y,&z);
add(x,y,z);
}
dijkstra(1);
if(dis[N]!=-INF) cout<<dis[N]<<endl;
else cout<<-1<<endl;
return 0;
}
//SPFA
#include<iostream>
#include<queue>
#include<algorithm>
#include<set>
#include<cmath>
#include<vector>
#include<map>
#include<stack>
#include<bitset>
#include<cstdio>
#include<cstring>
#define Swap(a,b) a^=b^=a^=b
#define cini(n) scanf("%d",&n)
#define cinl(n) scanf("%lld",&n)
#define cinc(n) scanf("%c",&n)
#define cins(s) scanf("%s",s)
#define coui(n) printf("%d",n)
#define couc(n) printf("%c",n)
#define coul(n) printf("%lld",n)
#define speed ios_base::sync_with_stdio(0)
#define Max(a,b) a>b?a:b
#define Min(a,b) a<b?a:b
#define mem(n,x) memset(n,x,sizeof(n))
#define INF 0x3f3f3f3f
#define maxn 100010
#define Ege 100000000
#define Vertex 1005
#define esp 1e-9
#define mp(a,b) make_pair(a,b)
using namespace std;
typedef long long ll;
typedef pair<int,int> PII;
struct Node
{
int to, lat, val; //边的右端点，边下一条边，边权
};
Node edge[1000005];
int head[1005],tot,dis[1005],N,M,vis[1005];
void add(int from, int to, int dis)
{
edge[++tot].lat = head[from];
edge[tot].to = to;
edge[tot].val = dis;
head[from] = tot;
}
void spfa(int s)
{
for(int i=0;i<=N;i++) dis[i]=-INF;
dis[0]=0;
memset(vis, 0, sizeof(vis));
vis[s] = 1;
dis[s] = 0;
queue<int>Q;
Q.push(s);
while (!Q.empty())
{
int u = Q.front();
Q.pop();
vis[u] = 0;
for (int i = head[u]; i; i = edge[i].lat)
{
int to = edge[i].to;
int di = edge[i].val;
if (dis[to]<dis[u] + di)
{
dis[to] = dis[u] + di;
if (!vis[to])
{
vis[to] = 1;
Q.push(to);
}
}
}
}
}
int main()
{
int t, x;
memset(head, 0, sizeof(head));
cini(N),cini(M);
while (M--)
{
int a, b, dis;
scanf("%d %d %d", &a, &b, &dis);
add(a, b, dis);
}
spfa(1);
if(dis[N]==-INF) {return cout<<-1<<endl,0;}
cout<<dis[N]<<endl;
return 0;
}