首页 > 代码库 > bzoj2750: [HAOI2012]Road
bzoj2750: [HAOI2012]Road
2750: [HAOI2012]Road
Time Limit: 10 Sec Memory Limit: 128 MBSubmit: 651 Solved: 302
[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
1 2 5
2 3 5
3 4 5
1 4 8
Sample Output
2
3
2
1
3
2
1
建出最短路图。。然后答案就是起点到这个点的最短路径乘以这个点到终点的最短路径。。
但是觉得挺难写的TAT
然后发现了dij的新姿势。。
扔个链接 http://www.cnblogs.com/zyfzyf/p/3995257.html
dijkstra算法可以在算出最短路的同时将点的源点的距离排序，然后按照这个
从前往后枚举在最短路上的边可以得到源点到每个点的最短路的数目，记为a[i]
从后往前枚举在最短路上的边可以得到经过每个点有多少条最短路，记为b[i]
然后对于每条边就是 +=a[e[i].from]*b[e[i].go]
1 #include<bits/stdc++.h> 2 #define rep(i,l,r) for(int i=l;i<=r;++i) 3 #define pa pair<int,int> 4 using namespace std; 5 const int N=5005; 6 typedef long long ll; 7 const ll ccz=1000000007; 8 int head[N],tot,dis[N],u,v,w,n,m,cnt,c[N]; 9 ll a[N],b[N],ans[N];10 struct zs{11 int to,next,w,id;12 }e[N];13 bool in[N];14 inline void ins(int u,int v,int w,int id){15 e[++tot].to=v; e[tot].next=head[u]; head[u]=tot; e[tot].w=w; e[tot].id=id;16 }17 inline void run(int s){18 priority_queue<pa,vector<pa>,greater<pa> >q;19 memset(in,0,sizeof in);20 memset(dis,60,sizeof dis); dis[s]=0; q.push(make_pair(0,s));21 cnt=0;22 while(!q.empty()){23 int x=q.top().second; q.pop();24 if(in[x]) continue; in[x]=1; c[++cnt]=x;25 for(int k=head[x];k;k=e[k].next) if(dis[x]+e[k].w<dis[e[k].to]) {26 dis[e[k].to]=e[k].w+dis[x];27 q.push(make_pair(dis[e[k].to],e[k].to));28 }29 }30 memset(a,0,sizeof a); memset(b,0,sizeof b);31 rep(i,1,cnt) b[c[i]]=1;32 a[s]=1;33 rep(i,1,cnt) for(int k=head[c[i]];k;k=e[k].next) if(dis[c[i]]+e[k].w==dis[e[k].to])(a[e[k].to]+=a[c[i]])%=ccz;34 for(int i=cnt;i;i--) for(int k=head[c[i]];k;k=e[k].next) if(dis[c[i]]+e[k].w==dis[e[k].to])(b[c[i]]+=b[e[k].to])%=ccz;35 rep(i,1,n) for(int k=head[i];k;k=e[k].next) if(dis[i]+e[k].w==dis[e[k].to])(ans[e[k].id]+=a[i]*b[e[k].to])%=ccz;36 }37 int main(){38 scanf("%d%d",&n,&m);39 rep(i,1,m) scanf("%d%d%d",&u,&v,&w),ins(u,v,w,i);40 rep(i,1,n) run(i);41 rep(i,1,m) printf("%lld\n",ans[i]);42 }
bzoj2750: [HAOI2012]Road
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。