HDU 6026 Deleting Edges(DAG)

Deleting Edges

Time Limit: 2000/1000 MS (Java/Others)    Memory Limit: 131072/131072 K (Java/Others)

Total Submission(s): 1188    Accepted Submission(s): 420

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  

題解：
選出最短路的路線，然後計算每個點的入度，因為入度是最短路，是以從中随意選取一條即可，
是以解便是所有入度的乘積。
代碼：

#include<bits/stdc++.h>
using namespace std;
const int maxn=55;
#define ll long long
const ll mod=1e9+7;
int rode[maxn][maxn],d[maxn],n;
char t[maxn][maxn];
ll num[maxn],in[maxn];
bool vis[maxn];
void dja()
{
    for(int i=0;i<maxn;i++)d[i]=1e9;
    memset(vis,0,sizeof(vis));d[0]=0;
    in[0]=1;
    while(1)
    {
        int v=-1;
        for(int i=0;i<n;i++)
            if(!vis[i]&&(v==-1||d[v]>d[i]))v=i;
        if(v==-1)break;
        vis[v]=1;
        for(int i=0;i<n;i++)
        {
            if(vis[i])continue;
            if(d[i]>d[v]+rode[v][i])
            {
                d[i]=d[v]+rode[v][i];
                in[i]=1;
            }
            else if(d[i]==d[v]+rode[v][i])
            {
                in[i]++;
            }
        }
    }
}
int main()
{
    while(~scanf("%d",&n))
    {
        for(int i=0;i<n;i++)scanf("%s",&t[i]);
        for(int i=0;i<n;i++)
            for(int j=0;j<n;j++)
            {
                rode[i][j]=t[i][j]-'0';
                if(rode[i][j]==0)rode[i][j]=1e9;
            }
        memset(in,0,sizeof(in));
        dja();
        ll ans=1;
        for(int i=0;i<n;i++)ans=ans*in[i]%mod;
        for(int i=0;i<n;i++)if(d[i]>1e7)ans=0;
        printf("%lld\n",ans);
    }
    return 0;
}