2750: [HAOI2012]Road

Time Limit: 10 Sec  Memory Limit: 128 MB

Submit: 651  Solved: 302

[][][]

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

简而言之，这道题就是求每个边在构建最短路用了多少次（有几个最短路包含这个边）

感觉很麻烦，既然是最短路，可以先分别以每个点为起点，求出最短路数组d[i]（从起点到每个点最短路的距离）;

然后考虑怎么算一个边用了几次；

首先前提是这个边是最短路上的边

即：d[i]+val==d[v]（起点到点i的最短路加上点i到点v的路，如果等于起点到点v的最短路，则满足）

然后可以有一个a[i]数组，记录起点到点i的最短路数；

一个b[i]数组，记录每个点i（意义和上行i一样）到其余点的最短路数；

然后怎么求这两个数组：

计算肯定有一定顺序，不然可能会重复计算，

由于与起点相连的最小边肯定是 至少一条最短路上的 边（与起点相连的最小边一定是组成最小路的边）

原因就是 djste djksl  ....dj算法的证明（英语不好）

然后就可以用这条边连的点进行扩展，即可求出a数组

b数组求法同理，但要倒着找，应为后面节点（后面节点概念看下面）的最短路肯定比前面节点的最短路少；

所谓后面节点，就是指节点被dj算法扔进堆里的顺序；

详见代码注释；代码如下：

　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　少女祈祷中......

#include 
     
      #include 
      
       #include 
       
        #include 
        
          using namespace std;const int N=5010;const int mod=1000000007; int n,m;int c[N],d[N];bool vis[N];long long ans[N],a[N],b[N];struct data{    int v,nxt,val,num;}edge[N];int cnt,alist[N];inline void add(int u,int v,int val,int num){    edge[++cnt].v=v;edge[cnt].val=val;edge[cnt].num=num;    edge[cnt].nxt=alist[u];alist[u]=cnt;}struct nod{    int num,val;    friend bool operator <(nod a,nod b){
   return a.val>b.val;}};void dj(int s){    priority_queue
         
           q;    memset(vis,false,sizeof vis);memset(d,0x3f3f3f3f,sizeof d);    nod sx; sx.num=s; sx.val=0;    d[s]=0;q.push(sx);    int tot=0;    while(!q.empty())    {        int num=q.top().num;q.pop();        if(vis[num]) continue;        vis[num]=true;c[++tot]=num;　　　　　　　　//c数组记录遍历顺序，即与远点距离顺序，先记录的距离近        int nxt=alist[num];　　　　　　　　　　　　　//num不是边的序号，是点！！！        while(nxt)        {            int val=edge[nxt].val;            int v=edge[nxt].v;            if(d[num]+val
         
        
       
      
     

 求推荐...