题目：点击打开链接 题意：n个顶点编号为0到n-1的图，从中删去一些边形成一棵树，保证树上任意一个点到0点的距离等于原图中0到这个点的最短路长度。求这棵树有多少种画法。
分析：（HDU 6026原题）先计算每个点到原点的最短距离，对于任意一个非原点，考虑给其选择一个父亲，使得父亲到原点的距离+两点距离=自己到原点距离。每个点可能的父亲的数量的乘积就是答案。可以想象成三角形用两条短边替换一条长边。因为n比较小，dijkstra或者floyd都行。
dijkstra代码：
#pragma comment(linker, "/STACK:102400000,102400000")///手动扩栈
#include<algorithm>
#include<iostream>
#include<cstdlib>
#include<cstring>
#include<cassert>
#include<string>
#include<cstdio>
#include<bitset>
#include<vector>
#include<cmath>
#include<ctime>
#include<stack>
#include<queue>
#include<deque>
#include<list>
#include<set>
#include<map>
using namespace std;
#define debug test
#define mst(ss,b) memset((ss),(b),sizeof(ss))
#define rep(i,a,n) for (int i=a;i<n;i++)
#define per(i,a,n) for (int i=n-1;i>=a;i--)
#define all(x) (x).begin(),(x).end()
#define fi first
#define se second
#define SZ(x) ((int)(x).size())
#define ll long long
#define ull unsigned long long
#define pb push_back
#define mp make_pair
#define INF 0x3f3f3f3f
#define eps 1e-10
#define PI acos(-1.0)
typedef pair<int,int> PII;
const ll mod = 1e9+7;
const int N = 1e2+10;
ll gcd(ll p,ll q){return q==0?p:gcd(q,p%q);}
ll qp(ll a,ll b) {ll res=1;a%=mod; assert(b>=0); for(;b;b>>=1){if(b&1)res=res*a%mod;a=a*a%mod;}return res;}
int to[4][2]={{-1,0},{1,0},{0,-1},{0,1}};
int n,e[N][N],d[N];
bool vis[N];
void dij(int n){
memset(vis, false, sizeof(vis));
memset(d, INF, sizeof(d));
d[0] = 0;
vis[0] = true;
for (int i = 1; i <= n - 1; i++){
int u = 0, MIN = INF;
for (int j = 0; j < n; j++){
if (!vis[j] && d[j] < MIN){
MIN = d[j];
u = j;
}
}
vis[u] = true;
for (int v = 0; v < n; v++){
if (!vis[v]){
if (d[v] > d[u] + e[u][v])
d[v] = d[u] + e[u][v];
}
}
}
}
int main(){
while (scanf("%d", &n) != EOF){
for (int i = 0; i < n; i++)
for (int j = 0; j < n; j++){
char ch;
scanf(" %c", &ch);
e[i][j] = ch - '0';
if (e[i][j] == 0 && i != j) e[i][j] = INF;
}
dij(n);
ll ans = 1;
for (int i = 1; i < n; i++){
ll cnt = 0;
for (int j = 0; j < n; j++){
if (e[i][j] && d[i] == d[j] + e[j][i])
cnt++;
}
ans = ans * cnt % mod;
}
printf("%lld\n", ans);
}
return 0;
}
floyd代码：
#include <vector>
#include <list>
#include <map>
#include <set>
#include <deque>
#include <stack>
#include <bitset>
#include <algorithm>
#include <functional>
#include <numeric>
#include <utility>
#include <sstream>
#include <iostream>
#include <iomanip>
#include <cstdio>
#include <cstring>
#include <cmath>
#include <cstdlib>
#include <ctime>
#define LL long long
#define pi 3.1415926535897932384626433
using namespace std;
const int maxn = 105;
const int inf = 100000000;
const int base = 1000000007;
int g[maxn][maxn], f[maxn][maxn];
int fa[maxn];
vector<string> init;
class TreesCount{
public:
int count(vector <string>);
}G;
int TreesCount::count(vector <string> graph){
int n = graph.size();
for (int i = 0; i < n; i ++)
for (int j = 0; j < n; j ++){
g[i][j] = graph[i][j] - 48;
if (! g[i][j]) g[i][j] = inf;
f[i][j] = g[i][j];
}
//floyd
for (int k = 0; k < n; k ++)
for (int i = 0; i < n; i ++)
for (int j = 0; j < n; j ++)
if (i != k && i != j && j != k)
g[i][j] = min(g[i][j], g[i][k] + g[k][j]);
//insert
g[0][0] = 0;
memset(fa, 0, sizeof(fa));
for (int i = 0; i < n; i ++)
for (int j = 0; j < n; j ++)
if (i != j && g[0][i] + f[i][j] == g[0][j])
fa[j] ++;
int ans = 1;
for (int i = 1; i < n; i ++)
ans = ((LL) ans * (LL) fa[i]) % (LL) base;
return ans;
}
int main(){
int n;
while (scanf("%d",&n)!=EOF){
init.clear();
for (int i = 1; i <= n; i ++){
string s; cin >> s;
init.push_back(s);
}
cout << G.count(init) << endl;
}
return 0;
}
