把 #P3371. 【模板】单源最短路径（弱化版）（题解） 的代码复制过来，然后改我注释标的地方就行了

注意：有负边权，所以不能用 Dijkstra

代码

#include <bits/stdc++.h>
using namespace std;
const int N = 1505,M = 50005,INF = 0x80000000;	// 改这里

// 链式前向星
struct edge{
	int u,v,w,prev;
}edges[M];
int tail[N],tot;
void add_edge(int u,int v,int w){
	edges[++tot] = {u,v,w,tail[u]};
	tail[u] = tot;
}

int dis[N],n,m,s = 1;
bool f[N];
void bf(){
	queue<int> q;
	q.push(s);
	while (!q.empty()){
		int u = q.front();
		q.pop();
		f[u] = 0;
		for (int j = tail[u];j;j = edges[j].prev){
			int v = edges[j].v,w = edges[j].w;
			if (dis[u] + w > dis[v]){	// 改这里
				dis[v] = dis[u] + w;
				if (!f[v])	q.push(v),f[v] = 1;
			}
		}
	}
}
int main(int argc, char **argv){
	fill(dis,dis + N,INF);
	cin >> n >> m;
	dis[s] = 0;
	for (int i = 0;i < m;i++){
		int u,v,w;
		cin >> u >> v >> w;
		add_edge(u,v,w);
	}
	bf();
	cout << (dis[n] == INF?-1:dis[n]);	// 改这里
	return 0;
}

题意

求最长路

思路

spfa的代码的大小号反改

正无穷改为负无穷就可以了

代码

#include<iostream>
#include<cstring>
#include<queue>
#define N 314514
#define INF 0x3fffffff
using namespace std;
int t,n,m;
struct ed
{
    int u,v,w;
    int next;
};
ed edge[N];
int h[N],tot;
void push(int u,int v,int w)
{
    edge[++tot]={u,v,w,h[u]};
    h[u]=tot;
}
int dis[N];
int vis[N];
queue<int>q;
void spfa()
{
    dis[1]=0;
    q.push(1);
    while(!q.empty())
    {
        int u=q.front();
        q.pop();
        vis[u]=0;
        for(int j=h[u];j;j=edge[j].next)
        {
            int v=edge[j].v;
            int w=edge[j].w;
            if(dis[v]<dis[u]+w)//改一下
            {
                dis[v]=dis[u]+w;
                if(!vis[v])
                {
                    q.push(v);
                    vis[v]=1;
                }
            }
        }
    }
}
int main()
{
    fill(dis,dis+N,-INF);//负无穷
    cin>>n>>m;
    for(int i=1;i<=m;i++)
    {
        int u,v,w;
        cin>>u>>v>>w;
        push(u,v,w);
    }
    spfa();
    if(dis[n]==-INF)//特判
        cout<<-1;
    else
        cout<<dis[n];
    return 0;
}