struct Int{
    int val;

    operator int() const{return val;}

    Int(int val = 0):val(val){
        val %= MOD; if (val < 0) val += MOD;
    }
    inline Int& operator +=(const Int& rhs){
        INC(val, rhs);
        return *this;
    }
    inline Int operator +(const Int& rhs) const{
        return sum(val, rhs.val);
    }
    inline Int operator -(const Int& rhs) const{
        return dff(val, rhs);
    }
    inline Int& operator *=(const Int& rhs){
        MUL(val, rhs);
        return *this;
    }
};

const int N = 50;

int D[N][N], G[N][N];

class TreesCount {
public:
	int count(vector <string> graph) {

	    int n = SZ(graph); REP_2(i, j, n, n) G[i][j] = i != j && graph[i][j] == '0' ? INF : graph[i][j] - '0';
	    CPY(D, G); REP_3(k, i, j, n, n, n) checkMin(D[i][j], D[i][k] + D[k][j]);

		Int res = 1; FOR(i, 1, n){
		    Int t; REP(j, n) if (i != j) t += D[0][j] + G[j][i] == D[0][i];
		    res *= t;
		}

		return res;
	}
};

Posted by xiaodao
Category: TopCoder