你知道黑暗城堡有 个房间， 条可以制造的双向通道，以及每条通道的长度。
城堡是树形的并且满足下面的条件：
设 为如果所有的通道都被修建，第 号房间与第 号房间的最短路径长度；
而 为实际修建的树形城堡中第 号房间与第 号房间的路径长度；
要求对于所有整数 ()，有 成立。
你想知道有多少种不同的城堡修建方案。当然，你只需要输出答案对 取模之后的结果就行了。
第一行为两个由空格隔开的整数 ;
第二行到第 行为 个由空格隔开的整数 ：表示 号房间与 号房间之间的通道长度为 。
一个整数：不同的城堡修建方案数对 取模之后的结果。
4 6
1 2 1
1 3 2
1 4 3
2 3 1
2 4 2
3 4 1
6
1.if ((d[j] < min) && (d[j] > pre)) {//d可能存在多个相等的 取了其中一个就把pre更新为d 导致后面相等的d无法取到
当时懒得重新初始化v
if ((d[j]<min)&&(!v[j])) {min=d[j];k=j;}
2.取模问题
不强制类型转化？强制类型转化不是把位数高的转化为位数低的？即ll转为int
只要ans in p中有一个为ll 且%p 即AC
ll ans in p
ans = ans * in % p;
ll ans； int in，p；
ans = ans * in % p;
int ans；ll in，p；
ans = ans * in % p;
https://loj.ac/submission/636255
测试点10输出0 溢出
ll ans in
ans = ans * in;
https://loj.ac/submission/636259
int ans,in
ans=ans*in
https://loj.ac/submission/636264
int ans,in,p
ans=ans*in%p
AC#include<bits/stdc++.h>//sort依据结构体里一个元素的大小进行排序 #define inf 0x3f3f3f3f//3f #define ll long long //typedef long long ll; using namespace std; const ll p=(1LL<<31)-1; int n,m,d[1005],id[1005],v[1005],e[1005][1005]; void dist(){ memset(d,0x3f,sizeof(d)); d[1]=0; for(int i=2;i<=n;i++)d[i]=e[1][i]; for(int i=1;i<n;i++){ int min=inf,k; for(int j=2;j<=n;j++) if ((d[j]<min)&&(!v[j])) {min=d[j];k=j;} v[k]=1; for(int j=2;j<=n;j++) if ((!v[j])&&d[j]>d[k]+e[k][j]) d[j]=d[k]+e[k][j]; } } int main(){ scanf("%d%d",&n,&m); memset(e,0x3f,sizeof(e)); for(int i=1;i<=m;++i){ int x,y,c; cin>>x>>y>>c; e[x][y]=c; e[y][x]=c; } dist(); //for(int i=1;i<=n;i++) cout<<d[i]<<endl; int k,min=inf,pre=0; ll ans=1; memset(v,0,sizeof(v)); for(int i=0;i<n-1;i++){ ll in=0; if (i) pre=min; min=inf;//漏了 for (int j=2;j<=n;j++) if ((d[j]<min)&&(!v[j])) {min=d[j];k=j;}//d[j]>pre 可能存在多个相等的 //cout<<k<<endl; v[k]=1; for (int j=1;j<=n;j++) if (d[k]==d[j]+e[j][k]) in++;//(d[j]<=pre)&& ans=ans*in%p;//取模问题 } cout<<ans; return 0;}
WA 30分#include <bits/stdc++.h> #define inf 0x3f3f3f3f // 3f #define ll long long // typedef long long ll; using namespace std; const int p = (1LL << 31) - 1; int n, m, d[1005], id[1005], v[1005], e[1005][1005]; void dist() { memset(d, 0x3f, sizeof(d)); d[1] = 0; for (int i = 2; i <= n; i++) d[i] = e[1][i]; for (int i = 1; i < n; i++) { int min = inf, k; for (int j = 2; j <= n; j++) if ((d[j] < min) && (!v[j])) { min = d[j]; k = j; } v[k] = 1; for (int j = 2; j <= n; j++) if ((!v[j]) && d[j] > d[k] + e[k][j]) d[j] = d[k] + e[k][j]; } } int main() { scanf("%d%d", &n, &m); memset(e, 0x3f, sizeof(e)); for (int i = 1; i <= m; ++i) { int x, y, c; cin >> x >> y >> c; e[x][y] = c; e[y][x] = c; } dist(); // for(int i=1;i<=n;i++) cout<<d[i]<<endl; int k, min = inf, pre = 0; ll ans = 1; for (int i = 0; i < n - 1; i++) { int in = 0; if (i) pre = min; min = inf; //漏了 for (int j = 2; j <= n; j++) if ((d[j] < min) && (d[j] > pre)) { min = d[j]; k = j; } // cout<<k<<endl; for (int j = 1; j <= n; j++) if (d[k] == d[j] + e[j][k]) in++; //(d[j]<=pre)&& ans = ans * in % p; //取模问题 }
cout << ans; return 0; }
原文：https://www.cnblogs.com/wyh447154317/p/11665403.html