[HAOI2012]外星人

2749: [HAOI2012]外星人

Time Limit: 3 Sec Memory Limit: 128 MB
Submit: 743 Solved: 397
[Submit][Status][Discuss]

Description

Input

Output

输出test行，每行一个整数，表示答案。

Sample Input

1
2
2 2
3 1

Sample Output

HINT

Test<=50 Pi<=10^5,1<=Q1<=10^9

Source

爆零原因：两条最短路不同，当且仅当它们包含的道路序列不同

（引申义：肯定有最短路不止一条的）

求从一个点出发，到某个点的最短路个数是经典问题，用heap+dijkstra就可以解决。

设dis[i,j]表示i到j的最短距离，count[i,j]表示i到j的最短路径数目

若o是一条权值为w的u到v的有向边，那么若dis[i,u]+w+dis[v,j]=dis[i,j]，那么从i到j的经过o的最短路数目为count[i,u]*count[v,j]

这样便得出了60分算法，预处理出来dis数组和count数组，枚举i、j和o，统计答案。

复杂度O(n^2m)

60分算法超时的问题在于枚举点对，如何能避免枚举点对呢？

容易想到直接计算一个点为起点到所有点最短路对答案的贡献，首先将边沿正向走一遍，求从原点到每个点的最短路径个数，然后按距离远点距离从大到小的顺序沿反向边来贡献答案。这个我不说不清……理解了60分算法多想想还是能理解的。

#include<cstdio>
#include<cstring>
#include<queue>
#define pir pair<int,int>
using namespace std;

const int N=5010;
const int inf=0x3f3f3f3f;
const int mod=1e9+7;
struct edge{int v,w,next;}e[N<<1];int tot,head[N];
int n,m,dis[N],cnt[N],sum[N],ans[N],q[N];bool vis[N];

void add(int x,int y,int z){
    e[++tot].v=y;e[tot].w=z;e[tot].next=head[x];head[x]=tot;
}
//据说spfa跑得比dijkstra快 
void dijkstra(int S){
    memset(dis,inf,(n+1)<<2);
    memset(vis,0,(n+1)<<2);
    memset(cnt,0,(n+1)<<2);cnt[S]=1;
    priority_queue<pir,vector<pir>,greater<pir> >q;
    q.push(make_pair(dis[S]=0,S));
    while(!q.empty()){
        pir t=q.top();q.pop();
        int x=t.second;
        if(vis[x]) continue;
        vis[x]=1;
        for(int i=head[x];i;i=e[i].next){
            if(!vis[e[i].v]&&dis[e[i].v]>dis[x]+e[i].w){
                dis[e[i].v]=dis[x]+e[i].w;
                cnt[e[i].v]=cnt[x];
                q.push(make_pair(dis[e[i].v],e[i].v));
            }
            else if(dis[e[i].v]==dis[x]+e[i].w){
                cnt[e[i].v]+=cnt[x];
                cnt[e[i].v]%=mod;
            } 
        }
    }
}
int dfs(int x){
    if(sum[x]) return sum[x];
    sum[x]=1;
    for(int i=head[x];i;i=e[i].next){
        if(dis[e[i].v]!=dis[x]+e[i].w) continue;
        sum[x]+=dfs(e[i].v);
        ans[i]+=sum[e[i].v]*cnt[x];
        ans[i]%=mod;
    }
    return sum[x];
}
void init(){
    scanf("%d%d",&n,&m);
    for(int i=1,x,y,z;i<=m;i++){
        scanf("%d%d%d",&x,&y,&z);
        add(x,y,z);
    }
}
void work(){
    for(int i=1;i<=n;i++){
        memset(sum,0,(n+1)<<2);
        dijkstra(i);
        dfs(i);
    }
    for(int i=1;i<=m;i++) printf("%d
",ans[i]);
}
int main(){
    freopen("road.in","r",stdin);
    freopen("road.out","w",stdout);
    init();
    work();
    return 0;
}