spfa（最短路求解）

模板：

#include<iostream>

#include<cstdio>

#include<queue>

#include<cstring>

using namespace std;

const int maxn = 105;

const int maxm = 100005;

struct Edge{

    int to,w,next;

}edge[maxm<<1];

int tot = 0,dis[maxn],cnt[maxn],head[maxn];

void addedge(int u,int v,int w)

{

    edge[tot].to = v;edge[tot].w = w;edge[tot].next = head[u];

    head[u] = tot++;

}

void spfa(int st,int ed)

{

    int i;

    queue<int>que;

    while (!que.empty())    que.pop();

    memset(dis,0x3f3f3f3f,sizeof(dis));

    memset(cnt,0,sizeof(cnt));

    que.push(st);

    dis[st] = 0;

    cnt[st] = 1;

    while (!que.empty())

    {

        int u = que.front();

        que.pop();

        if (u == ed)    continue;

        for (i = head[u];i != -1;i = edge[i].next)

        {

            int v = edge[i].to;

            if (dis[u] + edge[i].w < dis[v])

            {

                dis[v] = dis[u] + edge[i].w;

                if (!cnt[v])    que.push(v);

                cnt[v] = cnt[u];

            }

            else if (dis[u] + edge[i].w == dis[v])

            {

                if (!cnt[v])    que.push(v);

                cnt[v] += cnt[u];

            }

        }

    }

}

int main()

{

    int N,M,S,E,u,v,w,i;

    memset(head,-1,sizeof(head));

    scanf("%d%d%d%d",&N,&M,&S,&E);

    while (M--)

    {

        scanf("%d%d%d",&u,&v,&w);

        addedge(u,v,w);

        addedge(v,u,w);

    }

    spfa(S,E);

    printf("%d %d\n",dis[E],cnt[E]);

    return 0;

}

也可以计算有多少个最小生成树