记录编号	305364	评测结果	AAAAAAAAAA
题目名称	[HAOI 2012]道路	最终得分	100
用户昵称	liu_runda	是否通过	通过
代码语言	C++	运行时间	3.695 s
提交时间	2016-09-10 20:02:42	内存使用	0.48 MiB

#include<cstdio>
#include<queue>
using namespace std;
const int maxm=5005,maxn=1505,mod=1000000007;
struct edge{
    int to,next,w;
}lst[maxm],lst2[maxm];int len=1,len2=1;
int first[maxn],first2[maxn];
int f1[maxn],f2[maxn],f3[maxm]; 
void addedge(int a,int b,int w){
    lst[len].to=b;
    lst[len].next=first[a];
    lst[len].w=w;
    first[a]=len++;
} 
void addedge2(int a,int b,int w){
    lst2[len2].to=b;
    lst2[len2].next=first2[a];
    lst2[len2].w=w;
    first2[a]=len2++;
}
struct node{
    int v,d;
    node(int _v,int _d){
        v=_v;d=_d;
    }
    bool operator <(const node &B)const{
        return d>B.d;
    }
};
int T;
int vis[maxn],dis[maxn];
void dijkstra(int s){
    priority_queue<node> q;
    q.push(node(s,0));
    while(!q.empty()){
        node tmp=q.top();q.pop();
        if(vis[tmp.v]==T)continue;
        vis[tmp.v]=T;dis[tmp.v]=tmp.d;
        for(int pt=first[tmp.v];pt;pt=lst[pt].next){
            if(vis[lst[pt].to]!=T)q.push(node(lst[pt].to,lst[pt].w+tmp.d));
        }
    }
}
void dfs1(int x){
    if(vis[x]==T)return;
    f1[x]=0;
    for(int pt=first2[x];pt;pt=lst2[pt].next){
        if(dis[lst2[pt].to]+lst2[pt].w==dis[x]){
            dfs1(lst2[pt].to);
            f1[x]+=f1[lst2[pt].to],f1[x]%=mod;
        }
    }
    vis[x]=T;
}
void dfs2(int x){
    if(vis[x]==T)return;
    f2[x]=1;
    for(int pt=first[x];pt;pt=lst[pt].next){
        if(dis[lst[pt].to]==dis[x]+lst[pt].w){
            dfs2(lst[pt].to);
            f2[x]+=f2[lst[pt].to],f2[x]%=mod;
        }
    }
    vis[x]=T;
}
int main(){
    freopen("roadsw.in","r",stdin);
    freopen("roadsw.out","w",stdout);
    int n,m;
    scanf("%d %d",&n,&m);
    int a,b,w;
    for(int i=1;i<=m;++i){
        scanf("%d %d %d",&a,&b,&w);
        addedge(a,b,w);addedge2(b,a,w); 
    } 
    for(int i=1;i<=n;++i){
        ++T;
        dijkstra(i);
        vis[i]=++T;
        f1[i]=1;
        for(int j=1;j<=n;++j)dfs1(j);
        ++T;
        dfs2(i);/*printf("\n");
        for(int j=1;j<=n;++j)printf("%d ",f1[j]);printf("\n"); 
        for(int j=1;j<=n;++j)printf("%d ",f2[j]);printf("\n");
        for(int j=1;j<=n;++j)printf("%d ",dis[j]);printf("\n");
        */
        for(int j=1;j<=n;++j){
            for(int pt=first[j];pt;pt=lst[pt].next){
                if(dis[j]+lst[pt].w==dis[lst[pt].to])f3[pt]=(f3[pt]+1LL*f1[j]*f2[lst[pt].to])%mod;
            }
        }
    }
    for(int i=1;i<=m;++i)printf("%d\n",f3[i]);
    fclose(stdin);fclose(stdout);
    return 0;
} 
/*
4 4
1 2 5
2 3 5
3 4 5
1 4 8
*/