洛谷P2505 [HAOI2012]道路（最短路计数）

传送门

早上模拟赛考这题，结果竟然看错题目了orz

然后下午看完题解自己做的时候空间开小了白WA了好久orz

首先，如果以$S$为起点，一条边$(u,v)$在最短路上，则$dis[u]+edge[i]=dis[v]$

那么我们先以每个点为起点跑一遍最短路

每一次跑完最短路，对于一条边$i$，考虑它的经过次数

首先得满足上面那个条件，然后设$a[u]$表示从$S$走到$u$的最短路的方案，$v$表示经过$v$的最短路的方案

那么$ans[i]+=a[u]*b[v]$

$a$数组可以一遍拓扑排序顺便求出来，$b$数组可以用记忆化搜索搞出来

然后每一次跑完最短路都求出$a$和$b$，如果一条边出现在了这一次的最短路图中，就更新它的答案

 //minamoto

 #include<iostream>

 #include<cstdio>

 #include<cstring>

 #include<queue>

 #define ll long long

 using namespace std;

 #define getc() (p1==p2&&(p2=(p1=buf)+fread(buf,1,1<<21,stdin),p1==p2)?EOF:*p1++)

 char buf[<<],*p1=buf,*p2=buf;

 template<class T>inline bool cmin(T&a,const T&b){return a>b?a=b,:;}

 inline int read(){

     #define num ch-'0'

     char ch;bool flag=;int res;

     while(!isdigit(ch=getc()))

     (ch=='-')&&(flag=true);

     for(res=num;isdigit(ch=getc());res=res*+num);

     (flag)&&(res=-res);

     #undef num

     return res;

 }

 const int N=,M=,mod=1e9+;

 struct node{

     int u,dis;

     node(){}

     node(int u,int dis):u(u),dis(dis){}

     inline bool operator <(const node &b)const

     {return dis>b.dis;}

 };

 priority_queue<node> q;

 int head[N],Next[M],ver[M],edge[M],from[M],tot,n;

 ll ans[M],a[M],b[M];int dis[N],vis[M],d[N];

 int st[N],h,t,m;

 inline void add(int u,int v,int e){

     ver[++tot]=v,Next[tot]=head[u],head[u]=tot,edge[tot]=e,from[tot]=u;

 }

 void dijkstra(int s){

     memset(dis,0x3f,sizeof(dis));

     memset(vis,,sizeof(vis));

     dis[s]=,q.push(node(s,));

     while(!q.empty()){

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

         if(vis[u]) continue;

         vis[u]=;

         for(int i=head[u];i;i=Next[i]){

             int v=ver[i];

             if(cmin(dis[v],dis[u]+edge[i]))

             q.push(node(v,dis[v]));

         }

     }

 }

 inline void inita(int s){

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

     for(int i=head[u];i;i=Next[i])

     if(dis[ver[i]]==dis[u]+edge[i]) ++d[ver[i]];

     st[h=t=]=s;

     while(h<=t){

         int u=st[h++];

         for(int i=head[u];i;i=Next[i]){

             int v=ver[i];

             if(dis[v]==dis[u]+edge[i]){

                 --d[v],(a[v]+=a[u])%=mod;

                 if(!d[v]) st[++t]=v;

             }

         }

     }

 }

 void initb(int u){

     b[u]=;

     for(int i=head[u];i;i=Next[i]){

         int v=ver[i];

         if(dis[v]==dis[u]+edge[i]){

             vis[i]=;

             if(!b[v]) initb(v);

             (b[u]+=b[v])%=mod;

         }

     }

 }

 int main(){

 //    freopen("testdata.in","r",stdin);

     n=read(),m=read();

     for(int i=,u,v,e;i<=m;++i)

     u=read(),v=read(),e=read(),add(u,v,e);

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

         dijkstra(i);

         memset(a,,sizeof(a));

         memset(b,,sizeof(b));

         memset(vis,,sizeof(vis));

         a[i]=,inita(i),initb(i);

         for(int j=;j<=m;++j)

         if(vis[j]) (ans[j]+=a[from[j]]*b[ver[j]])%=mod;

     }

     for(int i=;i<=m;++i) printf("%lld\n",ans[i]);

     return ;

 }

巴特西

洛谷P2505 [HAOI2012]道路（最短路计数）

最新文章

热门文章