最短パス生成ツリー

最短経路生成木は1本の木で、そのルートノードは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の拡張経路が1本の木であることがわかります(木の特性を満たしていて、1つの点には多くの子供ノードがあり、各点には1人の父親しかいません......)この木を抽出するのが最小経路生成木です
実はこれは難しくありません.ただ、彼はいくつかの結合問題を出すので、概念を明確にしたほうがいいです.
これは最短パスツリーのシナリオ数を求める問題です.

#include
#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
",ans);
}