学校网站建设项目背景,商务软文写作,制作网线水晶头线序,婚纱网站源代码题目链接#xff1a;hdu 6026 Deleting Edges 题意#xff1a; 给你n个点#xff0c;和一个邻接矩阵#xff0c;非0表示有边#xff0c;0表示没边。 现在让你删一些边#xff0c;构成一棵树#xff0c;使得每个点到0这个点的距离为没删边之前的最短路。 问有多少棵这样的…题目链接hdu 6026 Deleting Edges 题意 给你n个点和一个邻接矩阵非0表示有边0表示没边。 现在让你删一些边构成一棵树使得每个点到0这个点的距离为没删边之前的最短路。 问有多少棵这样的树。 题解 首先题意说从0点开始对每个点都最短路那么用单源最短路就能搞定。 如何来计数呢 对于每一个点我们记录能到底这点的最短路的条数那么能够成题目要求的那种树的数量就是 anscnt[1]*cnt[2]*...*cnt[n-1]。 1 #includecstdio2 #define F(i,a,b) for(int ia;ib;i)3 using namespace std;4 typedef long long ll;5 6 const int N55,inf1e97;7 int n,cnt[N],inq[N],dis[N],Q[1000];8 char mp[N][N];9
10 void spfa()
11 {
12 F(i,1,n)dis[i]inf,inq[i]0,cnt[i]0;
13 int head0,tail0;
14 inq[0]1,Q[0]0;
15 while(head!tail1)
16 {
17 int xQ[head];
18 inq[x]0;
19 F(v,1,n-1)if(mp[x][v]!0)
20 {
21 if(dis[v]dis[x]mp[x][v]-0)
22 {
23 cnt[v]1;
24 dis[v]dis[x]mp[x][v]-0;
25 if(inq[v]0)Q[tail]v,inq[v]1;
26 }else if(dis[v]dis[x]mp[x][v]-0)cnt[v];
27 }
28 }
29 }
30
31 int main()
32 {
33 while(~scanf(%d,n))
34 {
35 F(i,0,n-1)scanf(%s,mp[i]);
36 spfa();
37 ll ans1;
38 F(i,1,n-1)ansans*cnt[i]%inf;
39 printf(%lld\n,ans);
40 }
41 return 0;
42 } View Code 转载于:https://www.cnblogs.com/bin-gege/p/6873717.html
