- 题库 ：一本通
- 题号 ：1486
- 题目 ：黑暗城堡
- link ：
思路 ：这道题既然要求使加入生成树中的点到1号节点的距离最小，那么我们可以理解为题目要求一个最短路径生成树，那么我们可以从1号节点向每个节点跑一遍SPFA最短路，并记录下来。这道题中如果满足两个点i，j && dis[i] = dis[j] + f[i][j]（dis[i]表示第i个点到1号节点的最短距离，f[i][j]表示i向j连的直接路径的长度）那么就满足题目中的条件（生成树中的某个点到1号节点的路径等于从当前点到1号节点的最短路径），所以当前点的答案数++，最后再用乘法原理把他们的方案数乘起来。
证明一下为什么 dis[i] = dis[j] + f[i][j] 答案数就++ ：
如样例图所示：
我们手动模拟求得dis[1] = 0, dis[2] = 1, dis[3] = 2, dis[4] = 3（f的就不求了）
开始模拟：
- 第2号节点 ：枚举所有点，显而易见只有dis[2] = dis[1] + f[2][1]的这种情况（每个节点都会有这种情况的，即直接走最短路）
- 第3号节点 ：枚举所有点，显而易见有两种情况，一是直接走最短路（这里就不写了），二是经过2号节点，再到达1号节点dis[3] = dis[2] + f[3][2]
- 第4号节点 ：枚举所有点，显而易见有三种情况，一是直接走最短路（这里就不写了），二是经过2号节点，再到达1号节点dis[4] = dis[2] + f[4][2]，三是经过3号节点，再到达1号节点dis[4] = dis[3] + f[4][3]
综上所述，如果一个节点可以经过另一个节点到达1号节点，而且距离还是相同的，那么答案数就可以++了。这里采用了Floyed的思想
那个式子翻译成中文就是如果一个节点到1号节点的最短路 = 另一个和它有连边的节点到根节点的最短路 + 它们两个节点之间的直接距离，那么答案数++，而那条边要不然就是在最短路里，要不然就是另一种方案
code ：
1 #include2 #define INF 0x3f3f3f3f 3 using namespace std; 4 const long long MOD = pow(2, 31) - 1;//别忘了取膜 5 int n, m, x, y, num, head[1000001], vis[1000001]; 6 long long ans, z, dis[1000001], f[1001][1001];//这些变量最好开long long 7 struct node 8 { 9 int next, to;10 long long val;11 }stu[1000001];12 inline void add(int x, int y, int z)//标准链式向前星 13 {14 stu[++num].next = head[x];15 stu[num].to = y;16 stu[num].val = z;17 head[x] = num;18 return;19 }20 inline void spfa(int s)//SPFA最短路 21 {22 memset(vis, 0, sizeof(vis));23 memset(dis, INF, sizeof(dis));24 queue < int > pru;25 pru.push(s);26 dis[s] = 0;27 vis[s] = 1;28 while(!pru.empty())29 {30 int u = pru.front();31 pru.pop();32 vis[u] = 0;33 for(register int i = head[u]; i; i = stu[i].next)34 {35 int k = stu[i].to;36 if(dis[k] > dis[u] + stu[i].val)37 {38 dis[k] = dis[u] + stu[i].val;39 if(!vis[k])40 {41 vis[k] = 1;42 pru.push(k);43 }44 }45 }46 }47 return;48 }49 int main()50 {51 memset(f, INF, sizeof(f));//初始化 52 scanf("%d %d", &n, &m);53 for(register int i = 1; i <= m; ++i)54 {55 scanf("%d %d %lld", &x, &y, &z);56 add(x, y, z);//无向图 57 add(y, x, z);58 f[x][y] = f[y][x] = min(f[x][y], z);//取最小(不知道有没有毒瘤数据) 59 }60 spfa(1);//从1号节点出发 61 ans = 1;//初始化为1 62 for(register int i = 2; i <= n; ++i)//1号节点不算 63 {64 int sum = 0;//当前节点的方案数 65 for(register int j = 1; j <= n; ++j)//枚举 66 {67 if(dis[i] == dis[j] + f[i][j])//不解释 68 {69 ++sum;70 }71 }72 if(sum)//这里其实不需要特判，因为每个点都一定会有走最短路这种情况 73 {74 ans = ans * sum % MOD;//乘法原理 + 边乘边膜 75 }76 }77 printf("%lld", ans);78 return 0;79 }