LightOJ - 1074 Extended Traffic (SPFA+负环）

题意：N个点，分别有属于自己的N个busyness（简称b），两点间若有边，则边权为（ub-vb）^3。Q个查询，问从点1到该点的距离为多少。

分析：既然是差的三次方，那么可能有负边权的存在，自然有可能出现负环。第一次用Dijkstra做，没多想，样例过了就去交了，结果肯定是WA了。之后加入了对负环的判断。很明显，如果在SPFA的算法过程中，若点u进出队列的次数达到N（N次松弛操作），那么u肯定在负环中。此外，u的邻接点v的距离dist[v]也必然<3，因为dsit[u]可以取到一个极小值。通过dfs函数给这些邻接点也加上标记。最后查询时，若点v不可到达，距离小于3或被标记，都是不合法的情况。

#include<iostream>

#include<cstring>

#include<stdio.h>

#include<vector>

#include<string>

#include<algorithm>

#include<queue>

#include<cmath>

using namespace std;

typedef int LL;

const int MAXN = ;

const int MAXM = MAXN * MAXN;

const int INF = 0x3f3f3f3f;

queue<int>q;

int N,M;

struct Edge{

    int v,next;

    int w;

};

struct Spfa

{

    int N,M;

    bool inq[MAXN];

    int dp[MAXN],cnt[MAXN];

    int pre[MAXN];

    int head[MAXN],tot;

    int dis[MAXN];

    bool incir[MAXN];

    Edge edge[MAXM];

    void init(int n){

        N = n;

        tot = ;

        memset(head,-,sizeof(head));

        memset(cnt,,sizeof(cnt));

    }

    void Addedge(int u,int v,int w){

        edge[tot].v = v;

        edge[tot].w = w;

        edge[tot].next = head[u];

        head[u] = tot++;

    }

    void dfs(int pos){

        incir[pos] = true;

        for (int i = head[pos] ; i != - ; i = edge[i].next){

            int v = edge[i].v;

            if (!incir[v])

                dfs(v);

        }

    }

    void spfa(int s){

        memset(incir,false,sizeof(incir));

        memset(inq,false,sizeof(inq));

        for (int i =  ; i <= N ; i++) dis[i] = INF;

        while (!q.empty()) q.pop();

        q.push(s);

        dis[s] = ;

        cnt[s] = ;

        inq[s] = true;

        while (!q.empty()){

            int u = q.front(); q.pop();

            inq[u] = false;

            for (int i = head[u] ; i != - ; i = edge[i].next){

                int v = edge[i].v;

                if (incir[v]) continue;

                if (dis[v] > dis[u] + edge[i].w){

                    dis[v] = dis[u] + edge[i].w;

                    if (!inq[v]){

                        inq[v] = true;

                        cnt[v]++;

                        q.push(v);

                        if (cnt[v] >= N) dfs(v);

                    }

                }

            }

        }

    }

}G;

LL dist(LL a,LL b){

    LL t = b-a;

    return t*t*t;

}

LL p[MAXN];

#define LOCAL

int main()

{

    #ifdef LOCAL

        freopen("in.txt","r",stdin);

        freopen("out.txt","w",stdout);

       #endif

    int N,M,S,T,u,v,q,cas=;

    LL tmp,b;

    scanf("%d",&T);

    while(T--){

        scanf("%d",&N);

        G.init(N);

        for(int i=;i<=N;++i){

            scanf("%d",&p[i]);

        }

        scanf("%d",&M);

        for(int i=;i<=M;++i){

            scanf("%d%d",&u,&v);

            G.Addedge(u,v,dist(p[u],p[v]));

        }

        G.spfa();

        scanf("%d",&q);

        printf("Case %d:\n",cas++);

        for(int i=;i<=q;++i){

            scanf("%d",&v);

            if(G.dis[v]==INF || G.dis[v]<|| G.incir[v] ) printf("?\n");

            else printf("%d\n",G.dis[v]);

        }

    }

    return ;

}

巴特西

LightOJ - 1074 Extended Traffic (SPFA+负环）

最新文章

热门文章