最短路+拓扑序DP

　　orz zyf & lyd

　　统计每条边在多少条最短路径上……其实可以统计有多少条最短路径经过了x，以及y出发到达任意一个结束点有多少种走法（沿最短路）

　　我们可以用Dijkstra求出以 i 为起点的最短路径图，它是一个DAG，然后我们用dij扩展的顺序（一个拓扑序）来搞DP！

　　　　令a[x]表示从 i 沿最短路走到 x 的方案数，b[x]表示从 x 往出走，沿最短路走到任意一个结束结点的总方案（就是经过x的最短路条数？只不过只看后半段）

　　其实就是将最短路分开两半进行统计了……然后乘一下……

　　通过这题的思路可以搞CTSC2015 Day1 T1？

　　跪了，pq应该把<定义为a.d>b.d……唉真是傻逼了

 /**************************************************************

     Problem: 2750

     User: Tunix

     Language: C++

     Result: Accepted

     Time:2276 ms

     Memory:1388 kb

 ****************************************************************/

 //BZOJ 2750

 #include<queue>

 #include<vector>

 #include<cstdio>

 #include<cstring>

 #include<cstdlib>

 #include<iostream>

 #include<algorithm>

 #define rep(i,n) for(int i=0;i<n;++i)

 #define F(i,j,n) for(int i=j;i<=n;++i)

 #define D(i,j,n) for(int i=j;i>=n;--i)

 #define pb push_back

 using namespace std;

 inline int getint(){

     int v=,sign=; char ch=getchar();

     while(ch<''||ch>''){ if (ch=='-') sign=-; ch=getchar();}

     while(ch>=''&&ch<=''){ v=v*+ch-''; ch=getchar();}

     return v*sign;

 }

 const int N=,M=,INF=~0u>>;

 const int P=;

 typedef long long LL;

 /******************tamplate*********************/

 int to[M],next[M],len[M],head[N],cnt;

 void add(int x,int y,int z){

     to[++cnt]=y; next[cnt]=head[x]; head[x]=cnt; len[cnt]=z;

 }

 struct node{

     int x,d;

     bool operator < (const node &b)const{ return d>b.d;}

 };

 int n,m,v[N],a[N],b[N],c[N],d[N];

 priority_queue<node>Q;

 int ans[M];

 void dijkstra(int S){

     memset(d,0x3f,sizeof d);

     memset(v,,sizeof v);

     d[S]=;

     int t=;

     Q.push((node){S,});

     while(!Q.empty()){

         int x=Q.top().x; Q.pop();

         if (v[x]) continue;

         v[x]=++t;

         for(int i=head[x];i;i=next[i]){

             int y=to[i],l=len[i];

             if (d[y]>d[x]+l){

                 d[y]=d[x]+l;

                 Q.push((node){y,d[y]});

             }

         }

     }

     F(i,,n) if (v[i]) c[v[i]]=i;

     memset(a,,sizeof a); a[c[]]=;

     F(i,,n) b[i]=;

     F(x,,t)

         for(int i=head[c[x]];i;i=next[i])

             if (d[to[i]]==d[c[x]]+len[i])

                 a[to[i]]=(a[to[i]]+a[c[x]])%P;

     D(x,t,)

         for(int i=head[c[x]];i;i=next[i])

             if (d[to[i]]==d[c[x]]+len[i])

                 b[c[x]]=(b[c[x]]+b[to[i]])%P;

     F(x,,n)

         for(int i=head[x];i;i=next[i])

             if (d[to[i]]==d[x]+len[i])

                 ans[i]=(ans[i]+(LL)a[x]*b[to[i]]%P)%P;

 }

 int main(){

 #ifndef ONLINE_JUDGE

     freopen("2750.in","r",stdin);

     freopen("2750.out","w",stdout);

 #endif

     n=getint(); m=getint();

     F(i,,m){

         int x=getint(),y=getint(),z=getint();

         add(x,y,z);

     }

     F(i,,n) dijkstra(i);

     F(i,,m) printf("%d\n",ans[i]);

     return ;

 }

2750: [HAOI2012]Road

Time Limit: 10 Sec Memory Limit: 128 MB
Submit: 347 Solved: 155
[Submit][Status][Discuss]

Description

C
国有n座城市，城市之间通过m条单向道路连接。一条路径被称为最短路，当且仅当不存在从它的起点到终点的另外一条路径总长度比它小。两条最短路不同，当且
仅当它们包含的道路序列不同。我们需要对每条道路的重要性进行评估，评估方式为计算有多少条不同的最短路经过该道路。现在，这个任务交给了你。

Input

第一行包含两个正整数n、m
接下来m行每行包含三个正整数u、v、w，表示有一条从u到v长度为w的道路

Output

输出应有m行，第i行包含一个数，代表经过第i条道路的最短路的数目对1000000007取模后的结果

Sample Input

4 4
1 2 5
2 3 5
3 4 5
1 4 8

Sample Output

2
3
2
1

HINT

数据规模

30%的数据满足：n≤15、m≤30

60%的数据满足：n≤300、m≤1000

100%的数据满足：n≤1500、m≤5000、w≤10000

Source

[Submit][Status][Discuss]

秒客网

【BZOJ】【2750】【HAOI2012】Road