2750: [HAOI2012]Road
Time Limit: 10 Sec Memory Limit: 128 MBSubmit: 728 Solved: 349
[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
HINT
数据规模
30%的数据满足:n≤15、m≤30
60%的数据满足:n≤300、m≤1000
100%的数据满足:n≤1500、m≤5000、w≤10000
Source
- #include<cstdio>
- #include<cstring>
- #include<queue>
- #define pir pair<int,int>
- using namespace std;
- const int N=10010;
- 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*5],q[N*20];bool vis[N*5];
- void add(int x,int y,int z){
- e[++tot].v=y;e[tot].w=z;e[tot].next=head[x];head[x]=tot;
- }
- 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("roadsw.in","r",stdin);
- freopen("roadsw.out","w",stdout);
- init();
- work();
- return 0;
- }