Deleting Edges
Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 131072/131072 K (Java/Others)
Total Submission(s): 567 Accepted Submission(s): 210
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 nodes, labeled from 0 to . 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 edges.
(2) For every vertice , the distance between 0 and on the tree is equal to the length of shortest path from 0 to 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 and , 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 .
There is a bi-directional graph with nodes, labeled from 0 to . 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 edges.
(2) For every vertice , the distance between 0 and on the tree is equal to the length of shortest path from 0 to 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 and , 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 .
Input
The input contains several test cases, no more than 10 test cases.
In each test case, the first line contains an integer , denoting the number of nodes in the graph.
In the following lines, every line contains a string with characters. These strings describes the adjacency matrix of the graph. Suppose the -th number of the -th line is , if is a positive integer, there is an edge between and with length of , if , then there isn't any edge between and .
The input data ensure that the -th number of the -th line is always 0, and the -th number of the -th line is always equal to the -th number of the -th line.
In each test case, the first line contains an integer , denoting the number of nodes in the graph.
In the following lines, every line contains a string with characters. These strings describes the adjacency matrix of the graph. Suppose the -th number of the -th line is , if is a positive integer, there is an edge between and with length of , if , then there isn't any edge between and .
The input data ensure that the -th number of the -th line is always 0, and the -th number of the -th line is always equal to the -th number of the -th line.
Output
For each test case, print a single line containing a single integer, denoting the answer modulo .
Sample Input
2 01 10 4 0123 1012 2101 3210
Sample Output
1 6
Source
题意：给你一个图，让你删掉一些边后变成一棵树，这棵树的根是0号节点，要满足在树上从0到任意节点的最短距离和原图相等。问总共有多少种删法？
做法：
用dijkstra求出原图中0点到每个点的最短路的长度，再暴力的跑一遍判断能否通过别的点同样使得0点到当前点的距离仍是最短路径，如果有一个可替代点，则表示对于当前点存在一种可以删边的方法，将所有的可能删的方法相乘即可。
#include <iostream>
#include<cstring>
#include<string>
#include<cstdio>
#include<algorithm>
#include<cmath>
#include<deque>
#include<vector>
#define ll long long
#define inf 0x3f3f3f3f
#define mod 1000000007;
using namespace std;
int n;
int e[][];
int d[];
bool book[];
void dij()
{
memset(d,inf,sizeof(d));
memset(book,,sizeof(book));
for(int i=;i<=n;i++) d[i]=e[][i];
book[]=;
d[]=;
int k=-;
int mi=inf;
while()
{
k=-;
mi=inf;
for(int i=;i<=n;i++)
{
if(!book[i]&&d[i]<mi)
{
mi=d[i];
k=i;
}
}
if(k==-) break;
book[k]=;
for(int i=;i<=n;i++)
{
if(!book[i]&&d[i]>d[k]+e[k][i])
{
d[i]=d[k]+e[k][i];
}
}
}
}
int main()
{
while(~scanf("%d",&n))
{
char s[];
for(int i=;i<=n;i++)
{
cin>>s;
for(int j=;j<n;j++)
{
if(s[j]=='')
{
e[i][j+]=inf;
}
else e[i][j+]=s[j]-'';
}
}
dij();
ll ans=;
ll temp=;
for(int i=;i<=n;i++)
{
temp=;
for(int j=;j<=n;j++)
{
if(d[i]==d[j]+e[i][j])
{
temp++;
}
}
ans=(ans*temp)%mod;
}
printf("%lld\n",ans);
}
return ;
}