排列組合思想.
先跑一遍最短路, 再從1節點開始搜索, 假如搜到一個點的路徑長度等于最短路, 則記錄到達該點的路徑數 + 1.
最后遍歷一遍, ans *= rec[i]
輸出答案即可.
關鍵在于想到這個排列組合的思想.
#include<cstdio>
#include<cstring>
#include<algorithm>
#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_JUDGEfreopen("test.in","r",stdin);#endifL 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);
}
