T57274 黑暗城堡

传送门

思路：

　　先求出各个点到 1 的最短路径。分别用两个数组将最短路径记录下来（一个要用来排序）。按排序后的 dis 值从小到大枚举各点加入树有多少种方案，最后根据乘法原理把各个点的方案数乘起来就是答案。（实现起来会比较繁琐）

Code:

#include<iostream>

#include<cstdio>

#include<algorithm>

#include<set>

#include<cstring>

#include<string>

#include<deque>

#include<map>

#include<cmath>

#include<stack>

#include<vector>

#include<queue>

#include<cstdlib>

using namespace std;

#define lck_max(a,b) ((a)>(b)?(a):(b))

#define lck_min(a,b) ((a)<(b)?(a):(b))

typedef long long LL;

const int maxn=1e6+;

const int INF=1e9+;

const LL mod=(1LL<<)-;

inline LL read()

{

    LL kr=,xs=;

    char ls;

    ls=getchar();

    while(!isdigit(ls))

    {

        if(!(ls^))

            kr=-;

        ls=getchar();

    }

    while(isdigit(ls))

    {

        xs=(xs<<)+(xs<<)+(ls^);

        ls=getchar();

    }

    return xs*kr;

}

inline void out(LL xs)

{

    if(!xs) {putchar(); return;}

    if(xs<) putchar('-'),xs=-xs;

    int kr[],ls=;

    while(xs) kr[++ls]=xs%,xs/=;

    while(ls) putchar(kr[ls]+),ls--;

}

inline LL ksc(LL x,LL y)

{

    LL tmp=(x*y-(LL)((long double)x/mod*y+1.0e-8)*mod);

    return tmp< ? tmp+mod : tmp;

}

LL n,m,ans=,cnt,head[maxn<<],f[maxn<<],dis[maxn];

bool vis[maxn<<];

priority_queue<pair<LL,LL>,vector<pair<LL,LL> >,greater<pair<LL,LL> > > q;

struct node

{

    LL nex,to,w;

}t[maxn<<];

struct hh

{

    LL dis,num;

}T[maxn<<];

inline bool cmp(const hh&x,const hh&y)

{

    return x.dis<y.dis;

}

inline void add(LL nex,LL to,LL w)

{

    t[++cnt].nex=head[nex];

    t[cnt].to=to;

    t[cnt].w=w;

    head[nex]=cnt;

}

inline void dijkstra(LL s)

{

    for (LL i=;i<=n;i++) T[i].dis=INF;

    T[].dis=;

    q.push(make_pair(T[].dis,s));

    while(!q.empty())

    {

        LL u=q.top().second; q.pop();

        if(vis[u]) continue; vis[u]=true;

        for(LL i=head[u];i;i=t[i].nex)

        {

            LL v=t[i].to,w=t[i].w;

            if (T[v].dis>T[u].dis+w) {T[v].dis=T[u].dis+w;q.push(make_pair(T[v].dis,v));}

        }

    }

}

inline void dfs()

{

    memset(vis,false,sizeof(vis));

    vis[]=true;

    for(LL i=;i<=n;i++)

    {

        LL u=T[i].num;vis[u]=true;

        for(LL j=head[u];j;j=t[j].nex)

        {

            LL v=t[j].to;

            if(vis[v]&&dis[v]+t[j].w==T[i].dis) f[i]++;

        }

    }

}

LL x,y,z;

int main()

{

    n=read();m=read();

    for (LL i=;i<=m;i++)

        x=read(),y=read(),z=read(),add(x,y,z),add(y,x,z);

    dijkstra();

    for (LL i=;i<=n;i++) T[i].num=i,dis[i]=T[i].dis;

    std::sort(T+,T+n+,cmp);

    dfs();

    for(LL i=;i<=n;i++) ans=ksc(ans,f[i]);

    out(ans),putchar('\n');

}