【题目】
题目描述：
给出
n
n
n 个点，
m
m
m 条带权无向边，问你从
1
1
1 号点到
n
n
n 号点的最短路中有多少种走法？
输入格式：
第一行两个数
n
,
m
n,m
n,m 分别表示点的个数和边的个数。（
2
2
2 ≤
n
n
n ≤
5000
5000
5000，
1
1
1 ≤
m
m
m ≤
100000
100000
100000） 接下来
m
m
m 行，每行
3
3
3 个数
u
,
v
,
w
u,v,w
u,v,w 表示
u
u
u 号点到
v
v
v 号点有一条距离为
w
w
w 的边。（
1
1
1 ≤
u
,
v
u,v
u,v ≤
n
n
n，
0
0
0 ≤
w
w
w ≤
5000
5000
5000） 数据保证
1
1
1 号点能够到达
n
n
n 号点，点和边都可以被走多次。
输出格式：
如果有无穷种走法，输出
−
1
-1
−1。否则输出走法的方案数
m
o
d
mod
mod
1000000009
1000000009
1000000009。
样例数据：
输入 4 4 1 2 1 1 3 1 2 4 1 3 4 1
输出 2
【分析】
依旧是一个最短路计数模板题
不过这道题有一个新的东西：无穷种走法
那么怎样会是无穷种走法呢？由于没有负边权，所以只有当最短路中出现了边权为
0
0
0 边，就有无穷种走法
而现在的问题就是如何判断一条边是否在最短路之间出现过
其实也很简单，正着做一遍最短路（
d
d
d），倒着做一遍最短路（
d
i
s
dis
dis），如果
d
i
+
d
i
s
j
+
w
i
,
j
=
d
n
d_i+dis_j+w_{i,j}=d_n
di+disj+wi,j=dn，就出现过
然后其它的套模板就可以了
【代码】
#include<queue>
#include<cstdio>
#include<cstring>
#include<algorithm>
#define N 5005
#define M 500005
#define Mod 1000000009
#define inf 1061109567
using namespace std
;
int n
,m
,t
,tot
;
int d
[N
],num
[N
],dis
[N
];
int first
[N
],v
[M
],w
[M
],nxt
[M
];
priority_queue
<pair
<int,int> >q
;
pair
<int,int>edge
[M
];bool vis
[N
];
void add(int x
,int y
,int z
)
{
t
++;
nxt
[t
]=first
[x
];
first
[x
]=t
;
v
[t
]=y
;
w
[t
]=z
;
}
void dijkstra(int s
)
{
int x
,y
,i
;
memset(d
,0x3f,sizeof(d
));
d
[s
]=0;q
.push(make_pair(0,s
));
while(!q
.empty())
{
x
=q
.top().second
;q
.pop();
if(vis
[x
])continue;vis
[x
]=true;
for(i
=first
[x
];i
;i
=nxt
[i
])
{
y
=v
[i
];
if(d
[y
]>d
[x
]+w
[i
])
{
num
[y
]=num
[x
];
d
[y
]=d
[x
]+w
[i
];
q
.push(make_pair(-d
[y
],y
));
}
else if(d
[y
]==d
[x
]+w
[i
])
num
[y
]=(num
[y
]+num
[x
])%Mod
;
}
}
}
int main()
{
int x
,y
,z
,i
,j
;
scanf("%d%d",&n
,&m
);
for(i
=1;i
<=m
;++i
)
{
scanf("%d%d%d",&x
,&y
,&z
);
add(x
,y
,z
),add(y
,x
,z
);
if(!z
) edge
[++tot
]=make_pair(x
,y
);
}
dijkstra(n
);
memcpy(dis
,d
,sizeof(dis
));
memset(num
,0,sizeof(num
));
memset(vis
,false,sizeof(vis
));
num
[1]=1,dijkstra(1);
for(i
=1;i
<=tot
;++i
)
{
if(d
[edge
[i
].first
]+dis
[edge
[i
].second
]==d
[n
])
{
printf("-1");
return 0;
}
}
printf("%d",num
[n
]);
return 0;
}
