LightOJ 1074 spfa判断负环-白红宇

LightOJ 1074 spfa判断负环

阅读量：6415 次

发布时间：2019-06-23

本文共 1942 字，大约阅读时间需要 6 分钟。

题意是给出一个有向图给出一定的边可以求出边权求单源最短路如果<3 或者达不到输出问号不然输出dis[v]

一开始耿直的写了一个dij交上去还过了样例然后wa掉看了看题发现其中有负权边并且应该是可以达到负环的比如3->1->2->3 所以<3是判断这个点能否是负的或者它的确小于3

如果一个点在负环中那么dis[it]可以是无限小那么它所能到达的所有点都可以是无限小

使用spfa判断当一个点被证实是在负环中 dfs它把它与它能到达的所有的点标记

需要注意的是松弛的时候判断松弛边的起点有没有被标记如果它被标记过说明它能松弛的那个点一定也被标记过了那么就跳过这个边就可以了

#include
     
      #include
      
       #include
       
        #include
        #include
         
          #include
          
           using namespace std;int a[205];int n,m,q;struct node{ int v; int w; int nex;};int l(int x){ return x*x*x;}node b[40050];int point[205];int cnt;void add(int u,int v,int w){ b[cnt].v=v; b[cnt].w=w; b[cnt].nex=point[u]; point[u]=cnt; cnt++;}bool vis[205];int dis[205];int c[205];bool f[205];void dfs(int u){ f[u]=true; for(int tt=point[u];tt!=-1;tt=b[tt].nex) { int v=b[tt].v; if(f[v]==false) { dfs(v); } }}void spfa(){ for(int i=1;i<=n;i++) dis[i]=999999999; dis[1]=0; for(int i=1;i<=n;i++) vis[i]=true; for(int i=1;i<=n;i++) c[i]=0; for(int i=1;i<=n;i++) f[i]=false; vis[1]=false; c[1]++; queue
           
            q; q.push(1); while(!q.empty()) { int u=q.front();q.pop(); vis[u]=true; for(int tt=point[u];tt!=-1;tt=b[tt].nex) { int v=b[tt].v; int w=b[tt].w; if(dis[v]>dis[u]+w&&f[u]==false) /// 如果不加上f[u]==false 会超时 如果f[u]==true 那么说明它能到达的点（松弛的点）一定也是f[v]==true 了 { dis[v]=dis[u]+w; if(vis[v]) { vis[v]=false; c[v]++; if(c[v]>=n&&f[v]==false) { dfs(v); } else { q.push(v); } } } } }}int main(){int t;int tt=0;scanf("%d",&t);while(t--){ tt++; cnt=0; scanf("%d",&n); for(int i=1;i<=n;i++) point[i]=-1; for(int i=1;i<=n;i++) { scanf("%d",&a[i]); } scanf("%d",&m); for(int i=1;i<=m;i++) { int u,v; int w; scanf("%d%d",&u,&v); w=l(a[v]-a[u]); add(u,v,w); } scanf("%d",&q); spfa(); printf("Case %d:\n",tt); for(int i=1;i<=q;i++) { int x; scanf("%d",&x); int ans=dis[x]; if(ans<3||ans==999999999) printf("?\n"); else printf("%d\n",ans); }}}

转载于:https://www.cnblogs.com/rayrayrainrain/p/5554148.html

你可能感兴趣的文章