[BZOJ5109]大吉大利，晚上吃鸡！

  1 #include<iostream>
  2 #include<cstdio>
  3 #include<cstring>
  4 #include<queue>
  5 #include<algorithm>
  6 #define M 100010
  7 #define ll long long
  8 #define int long long
  9 using namespace std;
 10 int n,m,num,cnt,tim,S,T,root,tot;
 11 int head[M],dis[M],pre[M],l[M],r[M],a[M],b[M],c[M];
 12 int low[M],dfn[M],dig[M],f[M];
 13 ll ans;bool vis[M],flag[M],cut[M];
 14 struct point{int to,next,dis;}e[M<<1];
 15 void add(int from,int to,int dis)
 16 {
 17     e[++num].next=head[from];
 18     e[num].to=to;
 19     e[num].dis=dis;
 20     head[from]=num;
 21 }
 22 void SPFA(int s)
 23 {
 24     memset(dis,1,sizeof(dis));dis[s]=0;
 25     queue<int>q;q.push(s);
 26     while(!q.empty())
 27     {
 28         int x=q.front();q.pop();
 29         vis[x]=false;
 30         for(int i=head[x];i;i=e[i].next)
 31         {
 32             int to=e[i].to;
 33             if(dis[to]>dis[x]+e[i].dis)
 34             {
 35                 pre[to]=x;
 36                 dis[to]=dis[x]+e[i].dis;
 37                 if(!vis[to])
 38                 {
 39                     vis[to]=true;
 40                     q.push(to);
 41                 } 
 42             }
 43         }
 44     }
 45 }
 46 void Getgraph(int s)
 47 {
 48     memset(vis,0,sizeof(vis));
 49     queue<int>q;q.push(s);
 50     while(!q.empty())
 51     {
 52         int x=q.front();q.pop();flag[x]=true;
 53         for(int i=head[x];i;i=e[i].next)
 54         {
 55             int to=e[i].to;
 56             if(dis[x]==dis[to]+e[i].dis)
 57             {
 58                 if(!vis[to]) vis[to]=true,q.push(to);
 59                 a[++cnt]=to,b[cnt]=x,c[cnt]=e[i].dis;
 60             }
 61         }
 62     }
 63 }
 64 void topsort(int s,int opt)
 65 {
 66     queue<int>q;q.push(s);
 67     while(!q.empty())
 68     {
 69         int x=q.front();q.pop();flag[M]=true;
 70         for(int i=head[x];i;i=e[i].next)
 71         {
 72             int to=e[i].to;
 73             if(!opt) l[to]=max(l[to],l[x]);
 74             else r[to]=min(r[to],r[x]);
 75             if(--dig[to]==0) q.push(to);
 76         }
 77     }
 78 }
 79 void tarjan(int x)
 80 {
 81     int flag=0;
 82     dfn[x]=low[x]=++tim;
 83     for(int i=head[x];i;i=e[i].next)
 84     {
 85         int to=e[i].to;
 86         if(!dfn[to])
 87         {
 88             tarjan(to);
 89             low[x]=min(low[x],low[to]);
 90             if(dfn[x]<=low[to])
 91             {
 92                 flag++;
 93                 if(x!=root||flag>1)
 94                 {
 95                     if(!cut[x]) tot++;
 96                     cut[x]=true;
 97                 }
 98             }
 99         }
100         else low[x]=min(low[x],dfn[to]);
101     }
102 }
103 main()
104 {
105     scanf("%lld%lld%lld%lld",&n,&m,&S,&T);
106     for(int i=1;i<=m;i++)
107     {
108         int a,b,c;scanf("%lld%lld%lld",&a,&b,&c);
109         add(a,b,c),add(b,a,c);
110     }
111     SPFA(S);
112     if(dis[T]>1e13) {printf("%lld\n",1ll*n*(n-1)/2);return 0;}
113     Getgraph(T);
114     memset(head,0,sizeof(head)),num=0;
115     for(int i=1;i<=cnt;i++)
116     {
117         add(a[i],b[i],c[i]);
118         add(b[i],a[i],c[i]);
119     }
120     root=S,tarjan(S);
121     int len=0;
122     for(int i=T;i;i=pre[i]) f[i]=++len;
123     for(int i=T;i;i=pre[i]) f[i]=len-f[i]+1;
124     for(int i=1;i<=n;i++) l[i]=1,r[i]=len;
125     for(int i=T;i;i=pre[i]) l[i]=r[i]=f[i];
126     memset(head,0,sizeof(head)),num=0;
127     for(int i=1;i<=cnt;i++) add(a[i],b[i],c[i]);
128     topsort(S,0); 
129     memset(head,0,sizeof(head)),num=0;
130     for(int i=1;i<=cnt;i++) add(b[i],a[i],c[i]);
131     topsort(T,1);
132     int k=0;
133     if(!cut[S]) tot++;
134     if(!cut[T]) tot++;
135     for(int i=1;i<=n;i++) 
136     {
137         if(!flag[i]) ans+=tot;
138         else ans+=max(0ll,r[i]-l[i]-1);
139     }
140     printf("%lld\n",ans);
141     return 0;
142 }