Deleting Edges
Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 131072/131072 K (Java/Others) Total Submission(s): 18 Accepted Submission(s): 9
Problem Description
Little Q is crazy about graph theory, and now he creates a game about graphs and trees.
There is a bi-directional graph with
n
nodes, labeled from 0 to
n−1
. Every edge has its length, which is a positive integer ranged from 1 to 9.
Now, Little Q wants to delete some edges (or delete nothing) in the graph to get a new graph, which satisfies the following requirements:
(1) The new graph is a tree with
n−1
edges.
(2) For every vertice
v(0<v<n)
, the distance between 0 and
v
on the tree is equal to the length of shortest path from 0 to
v
in the original graph.
Little Q wonders the number of ways to delete edges to get such a satisfied graph. If there exists an edge between two nodes
i
and
j
, while in another graph there isn't such edge, then we regard the two graphs different.
Since the answer may be very large, please print the answer modulo
109+7
.
Input
The input contains several test cases, no more than 10 test cases.
In each test case, the first line contains an integer
n(1≤n≤50)
, denoting the number of nodes in the graph.
In the following
n
lines, every line contains a string with
n
characters. These strings describes the adjacency matrix of the graph. Suppose the
j
-th number of the
i
-th line is
c(0≤c≤9)
, if
c
is a positive integer, there is an edge between
i
and
j
with length of
c
, if
c=0
, then there isn't any edge between
i
and
j
.
The input data ensure that the
i
-th number of the
i
-th line is always 0, and the
j
-th number of the
i
-th line is always equal to the
i
-th number of the
j
-th line.
Output
For each test case, print a single line containing a single integer, denoting the answer modulo
109+7
.
Sample Input
2
01
10
4
0123
1012
2101
3210
Sample Output
1
6
Source
2017中国大学生程序设计竞赛 - 女生专场
——————————————————————————————————
题目的意思是给出一张图，求最短路数的个数有多少种
思路：求出最短路，在求最短路时记录到达每个点的方案数，结果就是所有点方案数之和
#include <iostream>
#include <cstdio>
#include <cstring>
#include <string>
#include <algorithm>
#include <cmath>
#include <map>
#include <cmath>
#include <set>
#include <stack>
#include <queue>
#include <vector>
#include <bitset>
#include <functional>
using namespace std;
#define LL long long
const int INF=0x3f3f3f3f;
const int mod=1e9+7;
int n,m;
int mp[55][55];
int dis[55];
int vis[55];
LL cnt[55];
struct node
{
int id,val;
friend bool operator<(node a,node b)
{
return a.val>b.val;
}
};
void djstl(int o)
{
memset(dis,INF,sizeof dis);
memset(vis,0,sizeof vis);
memset(cnt,0,sizeof cnt);
node f,d;
f.id=o,f.val=0;
priority_queue<node>q;
q.push(f);
vis[o]=cnt[o]=1,dis[o]=0;
while(!q.empty())
{
f=q.top();
q.pop();
vis[f.id]=1;
for(int i=0; i<n; i++)
{
if(!vis[i]&&f.val+mp[f.id][i]<dis[i])
{
dis[i]=f.val+mp[f.id][i];
cnt[i]=1;
d.id=i;
d.val=dis[i];
q.push(d);
}
else if(!vis[i]&&f.val+mp[f.id][i]==dis[i])
{
cnt[i]++;
}
}
}
}
int main()
{
char s[55];
while(~scanf("%d",&n))
{
memset(mp,INF,sizeof mp);
for(int i=0; i<n; i++)
{
scanf("%s",&s);
for(int j=0; j<n; j++)
if(s[j]!='0')
mp[i][j]=s[j]-'0';
}
djstl(0);
LL ans=1;
for(int i=0; i<n; i++)
{
ans*=cnt[i];
ans%=mod;
}
printf("%d\n",ans);
}
return 0;
}
