排列组合思想.
先跑一遍最短路, 再从1节点开始搜索, 假如搜到一个点的路径长度等于最短路, 则记录到达该点的路径数 + 1. 最后遍历一遍, ans *= rec[i] 输出答案即可. 关键在于想到这个排列组合的思想.#include#include #include #define F(x) for (L i=h[x],v=e[i].v,w=e[i].w;i;i=e[i].next,v=e[i].v,w=e[i].w) using namespace std;typedef long long L;void read(L &x) { x=0; char c=getchar(); for (;c<'0' || c>'9';c=getchar()); for (;'0'<=c && c<='9';c=getchar()) x=x*10+c-'0'; }const L Q=2147483647;const L maxn=1e3+10;const L maxm=maxn*maxn;struct edge { L v,w,next;} e[maxm];L tot=0,h[maxn];inline void add(L u,L v,L w) { e[++tot].v=v;e[tot].w=w;e[tot].next=h[u]; h[u]=tot; }L q[maxm],ql,qr,d[maxn];bool inq[maxn];void spfa(L s) { memset(inq,0,sizeof inq); memset(d,0x3f,sizeof d); ql=qr=1; q[qr]=s; d[s]=0; inq[s]=true; while (ql<=qr) { L u=q[ql++]; F(u) if (d[v]>d[u]+w) { d[v]=d[u]+w; if (!inq[v]) inq[v]=true,q[++qr]=v; } inq[u]=false; }}L sum[maxn];void check(L s) { memset(inq,0,sizeof inq); memset(sum,0,sizeof sum); ql=qr=1; q[qr]=s; d[s]=0; inq[s]=true; while (ql<=qr) { L u=q[ql++]; F(u) if (d[v]==d[u]+w) { sum[v]++; if (!inq[v]) inq[v]=true,q[++qr]=v; } }}int main() { #ifndef ONLINE_JUDGE freopen("test.in","r",stdin); #endif L n,m; read(n),read(m); for (L i=1;i<=m;++i) { L u,v,w; read(u),read(v),read(w); add(u,v,w),add(v,u,w); } spfa(1); check(1); L ans=1; for (L i=1;i<=n;++i) if (sum[i]) (ans*=sum[i])%=Q; printf("%lld\n",ans);}