P1807 最长路

dfs

#include <bits/stdc++.h>
using namespace std;
const int inf=0x3f3f3f3f;
const int N=1505;
const int M=5e4+5;

int h[N],ne[M],e[M],w[M],tot;
void add(int from,int to,int wi) {
    e[++tot]=to;
    ne[tot]=h[from];
    w[tot]=wi;
    h[from]=tot;
}

int n,m;
int dis[N];
int dfs(int now) {
    if(dis[now]!=-inf)return dis[now];
    if(now==n)return dis[now]=0;
    for(int i=h[now];i;i=ne[i]) {
        int to=e[i];
        if(dfs(to)!=-inf)
            dis[now]=max(dis[now],dfs(to)+w[i]);
    }
    return dis[now];
}

int main() {
    cin>>n>>m;
    for(int i=1;i<=n;i++)dis[i]=-inf;
    while(m--) {
        int x,y,wi;
        cin>>x>>y>>wi;
        add(x,y,wi);
    }
    int ans=dfs(1);
    if(ans==-inf)cout<<-1<<endl;
    else cout<<ans<<endl;
    return 0;
}

拓扑排序

#include <bits/stdc++.h>
using namespace std;
const int inf=0x3f3f3f3f;
const int N=1505;
const int M=5e4+5;

int h[N],ne[M],e[M],w[M],tot;
void add(int from,int to,int wi) {
    e[++tot]=to;
    ne[tot]=h[from];
    w[tot]=wi;
    h[from]=tot;
}

int n,m;
int dis[N],in[N];
void topsort() {
    queue<int>q;
    for(int i=1;i<=n;i++)dis[i]=-inf;
    for(int i=1;i<=n;i++)
        if(in[i]==0)q.push(i);
    dis[1]=0;
    while(!q.empty()) {
        int now=q.front();
        q.pop();
        for(int i=h[now];i;i=ne[i]) {
            int to=e[i];
            dis[to]=max(dis[to],dis[now]+w[i]);
            if(--in[to]==0)q.push(to);
        }
    }
    if(dis[n]<=-1e7)cout<<-1<<endl;
    else cout<<dis[n]<<endl;
}

int main() {
    cin>>n>>m;
    while(m--) {
        int x,y,wi;
        cin>>x>>y>>wi;
        add(x,y,wi);
        in[y]++;
    }
    topsort();
    return 0;
}

SPFA

这个算法可以卡掉的，至于能不能用，全看出题人。总之尽量用上面两种

#include <bits/stdc++.h>
using namespace std;
const int inf=0x3f3f3f3f;
const int N=1505;
const int M=5e4+5;

int h[N],ne[M],e[M],w[M],tot;
void add(int from,int to,int wi) {
    e[++tot]=to;
    ne[tot]=h[from];
    w[tot]=wi;
    h[from]=tot;
}

//spfa是可以卡掉的
int n,m;
int dis[N];
bool vis[N];
void spfa() {
    queue<int>q;
    for(int i=1;i<=n;i++)dis[i]=-inf;
    dis[1]=0;
    vis[1]=1;
    q.push(1);
    while(!q.empty()) {
        int now=q.front();
        vis[now]=0;
        q.pop();
        for(int i=h[now];i;i=ne[i]) {
            int to=e[i];
            if(dis[to]<dis[now]+w[i]) {
                dis[to]=dis[now]+w[i];
                if(vis[to]==0)q.push(to),vis[to]=1;
            }
        }
    }
    if(dis[n]<=-1e7)cout<<-1<<endl;//这里需要特别判断一下，不能是直接！=inf
    else cout<<dis[n]<<endl;
}

int main() {
    cin>>n>>m;
    while(m--) {
        int x,y,wi;
        cin>>x>>y>>wi;
        add(x,y,wi);
    }
    spfa();
    return 0;
}