图论--最长路--基于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;

}
巴特西

图论--最长路--基于SPFA的调整模板

最新文章

热门文章
