原题

代码

#include<bits/stdc++.h>
using namespace std;
int n,m,ds[1001],rd[1001][1001],t[1001],nw;
struct rd{
	int s,e,l;
}a[1001];
bool ok[1001];
void D(){
	for(int i=1;i<=n;i++){
		int u=n+1;
		for(int j=1;j<=n;j++)
			if(!ok[j]&&ds[j]<ds[u]) u=j;
		ok[u]=1;
		for(int j=1;j<=n;j++) 
			ds[j]=min(ds[j],ds[u]+rd[u][j]);
	}
}
int P(){
	int ans=1;
	for(int i=1;i<=n;i++)
		for(int j=2;j<=n;j++)
			if(i^j&&ds[j]==ds[i]+rd[j][i]) t[j]++,t[j]%=int(pow(2.,31)-1);//这里为什么要i^j???
	for(int i=2;i<=n;i++) ans*=t[i],ans%=int(pow(2.,31)-1);
	return ans;
}
int main(){
	cin>>n>>m;
	for(int i=1;i<=m;i++) cin>>a[i].s>>a[i].e>>a[i].l,rd[a[i].s][a[i].e]=rd[a[i].e][a[i].s]=a[i].l;
	for(int i=2;i<=n+2;i++) ds[i]=99999999;
	D();
	cout<<P();
	return 0;
}