Ural 1450 求最长路 SPFA

本是古典何须时尚 2021-12-10 16:37 235阅读 0赞

题意就是求S点到T点的有向无环图中的最长路。

用SPFA可以解决。

一开始一直RE的原因 QAQ

竟然是在开Edge 邻接表的时候开小了

改了一下4Y

#include <stdio.h>
    #include <string.h>
    #include <stdlib.h>
    #include <math.h>
    #include <iostream>
    #include <stack>
    #include <queue>
    #include <algorithm>
    
    #define ll long long
    using namespace std;
    const int INF = 0x3f3f3f3f;
    const int MAXN = 124799;
    const int MAXSIZE = 1002;
    
    int dis[MAXSIZE],head[MAXSIZE],vis[MAXSIZE];
    int n, cnt;
    
    struct node{
          int u,v,val,next;
    } Edge[MAXN];
    
    void addEdge(int u,int v,int val){
          Edge[cnt].u=u;
          Edge[cnt].v=v;
          Edge[cnt].val=val;
          Edge[cnt].next=head[u];
          head[u]=cnt++;
    }
    
    void init(){
        memset(head, -1, sizeof(head));
        memset(vis, 0, sizeof(vis));
        for(int i = 1; i <= n; ++i) dis[i] = -INF;
        cnt = 0;
    }
    
    int spfa(int src, int ter){
        queue<int>q;
        q.push(src);
        vis[src]=1;
        dis[src]=0;
        while(!q.empty()){
            int u=q.front();
            q.pop();
            vis[u]=0;
            for(int i=head[u]; i!=-1; i=Edge[i].next){
                int v=Edge[i].v;
                if(dis[v]<dis[u]+Edge[i].val){
                    dis[v]=dis[u]+Edge[i].val;
                    if(!vis[v]){
                        vis[v]=1;
                        q.push(v);
                    }
                }
            }
        }
        return dis[ter];
    }
    
    int main(){
        int i, j, k, t, numCase;
        int ss, ee, val;
        int s, e;
        while(EOF != scanf("%d%d",&n,&numCase)){
            init();
            while(numCase--){
                scanf("%d%d%d",&ss,&ee,&val);
                addEdge(ss,ee,val);
            }
            scanf("%d%d",&s,&e);
            int ans = spfa(s, e);
            if(ans > 0) printf("%d\n",spfa(s, e));
            else   printf("No solution\n");
        }
        return 0;
    }

转载于:https://www.cnblogs.com/wushuaiyi/p/3890050.html