C++14(g++5.4) 解法, 执行用时: 349ms, 内存消耗: 4360K, 提交时间: 2019-08-22 15:10:04
#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
const long long mod=(1LL<<31)-1;
int n,m;
const int N=1005;
int d[N],a[N][N],list[N];
bool v[N];
void dijkstra(){
memset(d,0x3f,sizeof(d));
memset(v,0,sizeof(v));
d[1]=0;
for(int i=1;i<n;i++){
int x=0;
for(int j=1;j<=n;j++){
if(!v[j]&&(!x||d[x]>d[j])){
x=j;
}
}
v[x]=1;
for(int y=1;y<=n;y++){
if(!v[y]){
d[y]=min(d[y],d[x]+a[x][y]);
}
}
}
}
bool cmp(int i,int j){
return d[i]<d[j];
}
int main(){
scanf("%d%d",&n,&m);
memset(a,0x3f,sizeof(a));
for(int i=1;i<=n;i++){
a[i][i]=0;
}
for(int i=1;i<=m;i++){
int x,y,z;
scanf("%d%d%d",&x,&y,&z);
a[x][y]=a[y][x]=min(a[x][y],z);
}
dijkstra();
for(int i=1;i<=n;i++){
list[i]=i;
}
sort(list+1,list+n+1,cmp);
long long res=1;
for(int i=2;i<=n;i++){
int tt=0;
for(int j=1;j<i;j++){
if(d[list[j]]+a[list[j]][list[i]]==d[list[i]]){
++tt;
}
}
res=(res*tt)%mod;
}
cout<<res<<endl;
return 0;
}
C++ 解法, 执行用时: 221ms, 内存消耗: 8244K, 提交时间: 2022-02-09 11:12:57
#include<bits/stdc++.h>
using namespace std;
long long dis[1010][1010],g[20000],cnt[20000],vis[2000000],n,m,ans=1,x,y,z;
int main(){
cin>>n>>m;
for(int i=1;i<=n;i++)for(int j=1;j<=n;j++){if(i==j)dis[i][j]=0;else dis[j][i]=dis[i][j]=1000000000000;}
for(int i=1;i<=m;i++){cin>>x>>y>>z;if(dis[x][y]>z)dis[x][y]=dis[y][x]=z;}
for(int i=1;i<=n;i++)g[i]=dis[1][i];
for(int i=1;i<=n;i++){
long long minn=1000000000000,u;
for(int j=1;j<=n;j++)if(!vis[j]&&minn>g[j])minn=g[j],u=j;
vis[u]=1;
for(int j=1;j<=n;j++)if(g[j]>dis[u][j]+g[u])g[j]=g[u]+dis[u][j];
}
for(int i=1;i<=n;i++)for(int j=1;j<=n;j++)if(i-j&&g[j]==g[i]+dis[i][j])cnt[j]++;
for(int i=1;i<=n;i++){if(!cnt[i])continue;ans*=cnt[i];ans%=2147483647;}
cout<<ans;
return 0;
}
的整数 i，有 
。为了打败 Lord lsp，lqr 想知道有多少种不同的城堡修建方案。于是 lqr 向 applepi 提出了这个问题。由于 applepi 还 要忙着出模拟赛，所以这个任务就交给你了。当然，你只需要输出答案对 
取模之后 的结果就行了