最短路径生成树

最短路径生成树是一棵树，它的根节点为S，在这棵树上跑dijkstra与在原图上跑得到的d会是完全一样的。
这棵树的生成可以用dijkstra来理解。每个未被标记的节点把d推priority_queue，取出堆顶x，x先被标记。
然后更新与x相连的节点，如果有d[y]>d[x]+e[k].c，那么把y节点以及k这条边一起选入预定的最小路径生成树。
当y被标记时，这条预定的边变成实际的最小路径生成树的一条边。
再理解一下，dijkstra看似随机的从priority_queue中随机的取点，实际上它取的点还是有原则的。
画一个图出来，YY一下，可以发现dijkstra的扩展路径就是一棵树，
（很满足树的特性，一个点有很多个孩子节点，每个点只有一个父亲……）把这棵树提取出来便是最小路径生成树啦

其实这个不难想到，只是他会出一些结合的题，所以还是明确一下概念比较好

这是一个求最短路径树的方案数的题

#include<bits/stdc++.h>
#define inf 1e12;
using namespace std;

int n,m,x,y,z;
long long dis[1010][1010],g[20000],cnt[20000];
bool vis[2000000]={0};

int main()
{
    scanf("%d%d",&n,&m);
    for(int i = 1;i <= n;i++)
        for(int j = 1;j <= n;j++)//一、预处理 
        {
            if(i == j) dis[i][j]=0;
            else dis[j][i] = dis[i][j] = inf;
        }
    for(int i = 1;i <= m;i++)
    {
        scanf("%d%d%d",&x,&y,&z);
        if(dis[x][y] > z)
            dis[x][y] = dis[y][x] = z; 
    }
    for(int i = 1;i <= n;i++) g[i]=dis[1][i];
    
    for(int i = 1;i <= n;i++)// 二、用迪杰斯特拉算法求出一号房间到每个房间的单源最短路 
    {
        long long minn = inf;
        int u;
        for(int j = 1;j <= n;j++)
        {
            if(!vis[j] && minn > g[j])
            {
                minn = g[j];
                u = j;
            }
        }    //最小边
        vis[u] = 1;
        for(int j = 1;j <= n;j++)
            if(g[j] > dis[u][j] + g[u])
                g[j] = g[u] + dis[u][j];
    }
    long long ans = 1;
    for(int i = 1;i <= n;i++)//三、方案累加 
        for(int j = 1;j <= n;j++)
            if(i != j && g[j] == g[i] + dis[i][j]) 
                cnt[j]++;
    for(int i = 1;i <= n;i++)
    {
        if(cnt[i] == 0) continue;
        ans *= cnt[i];
        ans %= 2147483647;
    }
    printf("%lld\n",ans);
}