牛奶销售

发表于 |
字数统计: 946 | 阅读时长 ≈ 5
  • Code Level : ※/※※※
  • Thingking Level: ※

Description

有向图，带负权，但环上不含负权边

Solution

  • 对于SPFA的优化:

可以使用SLF和LLL(对于此题，LLL似乎加上反而慢)

Code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
    #include<bits/stdc++.h>
    using namespace std;
    const int nn=500005; const int inf=0x3f3f3f3f;
    int n,p,r,s,t,f[nn],d[nn],vis[nn]; deque<int>q;
    struct al{
        int t,n,c;
    }e[nn*4];
    void ade(int x,int y,int z){e[++t]=(al){y,f[x],z};f[x]=t;}
    int main(){
        int i,x,y,z;
        scanf("%d%d%d%d",&n,&p,&r,&s);for(i=1;i<=p+r;i++){scanf("%d%d%d",&x,&y,&z);ade(x,y,z);if(i<=p)ade(y,x,z);}
        for(i=1;i<=n;i++) d[i]=inf; d[s]=0; q.push_front(s);
        while(!q.empty()){
            x=q.front();q.pop_front();vis[x]=0;
            for(int i=f[x];i;i=e[i].n){
            int t=e[i].t;
            if(d[t]>d[x]+e[i].c){
                d[t]=d[x]+e[i].c;
                if(!vis[t]){ vis[t]=1; if(q.empty()||d[t]<d[q.front()]) q.push_front(t);else q.push_back(t); }
            }
        }
    }
    for(i=1;i<=n;i++) if(d[i]==inf)printf("NO PATH\n"); else printf("%d\n",d[i]);
    return 0;
}

  • 对于题目特性的分析

  • 因为环上没有负权，意思是在环中是可以跑dijstra的。而对于负权边指向的点，只需要更新但不计入dijstra的松弛即可。
  • 对于环的计数，我们必须当一个环所有的父亲都跑完最短路的时候才能进行优化，所有需要缩点+DAG

Code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
#include<bits/stdc++.h>
using namespace std;
const int nn=1e4*5+5;
const int inf=0x3f3f3f3f;
int n,r,p,s,fl,t,k,f2[nn],f[nn],ti,df[nn],lo[nn],st[nn],fr,be[nn],rd[nn],t2,ds[nn],mi[nn],t3,f3[nn]; char c; queue<int>q; bool vis[nn],in[nn];
struct al{ int t,n,c; }e[nn*6],g[nn*6],e2[nn*6];
void adl(int x,int y,int z){e[++t]=(al){y,f[x],z};f[x]=t;}
void adm(int x,int y,int z){g[++t2]=(al){y,f2[x],z};f2[x]=t2;}
void adk(int x,int y){e2[++t3]=(al){y,f3[x],0};f3[x]=t3;}
void r_i(int &x){ x=0; c=getchar(); fl=0; for(;!isdigit(c);c=getchar())if(c=='-')fl=1; for(;isdigit(c);c=getchar())x=x*10-'0'+c; if(fl) x=-x;}
void ru(int no){
    df[no]=lo[no]=++ti;st[++fr]=no; int to; in[no]=1;
    for(int i=f[no];i;i=e[i].n){ to=e[i].t; if(in[to]){ if(!be[to]) lo[no]=min(lo[no],df[to]); continue ; } ru(to); lo[no]=min(lo[no],lo[to]); }
    if(df[no]==lo[no]){++k;while(st[fr]!=no)adk(k,st[fr]),be[st[fr--]]=k;adk(k,st[fr]),be[st[fr--]]=k;}
}
struct bt{
    int id,d; friend bool operator<(bt a,bt b){ return a.d>b.d; }
}; priority_queue<bt>pq; 
void di(int x){
    for(int i=f3[x];i;i=e2[i].n) pq.push((bt){e2[i].t,ds[e2[i].t]});
    while(!pq.empty()){
        bt y=pq.top(); pq.pop(); if(vis[y.id]) continue ; vis[y.id]=1;
        for(int i=f[y.id];i;i=e[i].n){
            int z=e[i].t; 
            if(ds[z]>ds[y.id]+e[i].c){
                ds[z]=ds[y.id]+e[i].c;
                if(be[z]==be[y.id]) pq.push((bt){z,ds[z]});
            }
        }
    }
}
int main(){
    r_i(n);r_i(r);r_i(p);r_i(s); int i,x,y,z;
    for(i=1;i<=r+p;i++){
        r_i(x);r_i(y);r_i(z);
        adl(x,y,z); if(i<=r)adl(y,x,z);
    } 
    ru(s); for(i=1;i<=n;i++) ds[i]=inf; ds[s]=0; 
    for(x=1;x<=n;x++)if(in[x]) for(i=f[x];i;i=e[i].n){y=be[x];z=be[e[i].t]; if(y!=z) rd[z]++,adm(y,z,e[i].c); } q.push(be[s]); adk(be[s],s); 
    while(!q.empty()){
        x=q.front(); q.pop(); di(x);//printf("%d %d\n",e2[i].t,ds[e2[i].t]);
        for(i=f2[x];i;i=g[i].n){ y=g[i].t;rd[y]--; if(!rd[y])q.push(y); }
    }
    for(i=1;i<=n;i++) if(ds[i]==inf) printf("NO PATH\n"); else printf("%d\n",ds[i]);
    return 0;
}