LightOJ 1074 Extended Traffic SPFA 消负环

时间：2023-03-09 06:33:07
LightOJ 1074 Extended Traffic SPFA 消负环

分析：一看就是求最短路，然后用dij，果断错了一发，发现是3次方，有可能会出现负环

然后用spfa判负环，然后标记负环所有可达的点，被标记的点答案都是“？”

#include<cstdio>

#include<cstring>

#include<queue>

#include<cstdlib>

#include<algorithm>

#include<vector>

#include<cmath>

using namespace std;

typedef long long LL;

const int N=+;

const int INF=0x7fffffff;

struct Edge{

   int v;

   LL w;

   int next;

   bool operator<(const Edge &e)const{

      return w>e.w;

   }

}edge[N*N];

int head[N],val[N],tot,n,m,p;

LL d[N];

void add(int u,int v,LL w){

   edge[tot].v=v;

   edge[tot].w=w;

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

   head[u]=tot++;

}

bool inq[N];

queue<int>q;

int cnt[N];

bool c[N];

void dfs(int u){

   c[u]=;

   for(int i=head[u];~i;i=edge[i].next)

     if(!c[edge[i].v])dfs(edge[i].v);

}

void spfa(int s){

   for(int i=;i<=n;++i)

     c[i]=cnt[i]=inq[i]=,d[i]=INF;

   q.push(s),cnt[s]=,inq[s]=,d[s]=;

   while(!q.empty()){

     int u=q.front();

     q.pop();

     inq[u]=;

     if(c[u])continue;

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

         int v=edge[i].v;

         if(c[v])continue;

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

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

           if(inq[v])continue;

            q.push(v);

            ++cnt[v];

            inq[v]=;

            if(cnt[v]>n)dfs(v);

         }

     }

   }

}

int main(){

   int T,cas=;

   scanf("%d",&T);

   while(T--){

     scanf("%d",&n);

     for(int i=;i<=n;++i)scanf("%d",&val[i]);

      scanf("%d",&m);

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

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

        int u,v;

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

        LL w=(val[v]-val[u]);

        w=w*w*w;

        add(u,v,w);

      }

      spfa();

      scanf("%d",&p);

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

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

         int u;

         scanf("%d",&u);

         if(c[u]||d[u]==INF||d[u]<)printf("?\n");

         else printf("%d\n",d[u]);

      }

   }

    return ;

}

相关文章