NC213880. CCA的期望
描述
输入描述
第一行三个正整数 n , m , k，意义同题面。第二行 n 个正整数 ，第 i 个数表示 i 好结点的初始颜色，0 为白色，1 为黑色。接下来的 m 行，每行三个正整数 u , v , w，表示有一条连接 u , v 的长度为 w 的无向边 。
输出描述
一行，一个正整数，表示被染黑的点数的期望对 1023694381 取模后的结果 。
示例1
输入:
3 2 1 0 0 0 1 2 1 2 3 2
输出:
682462923
C++(g++ 7.5.0) 解法, 执行用时: 378ms, 内存消耗: 2580K, 提交时间: 2022-10-25 15:33:26
#include<iostream>
using namespace std;
#define int long long
const int N=550,mod=1023694381;
int n,m,k;
int d[N][N],cnt[N],a[N];
int ksm(int a,int b)
{
int ans=1;
while(b)
{
if(b&1) ans=ans*a%mod;
b>>=1;
a=a*a%mod;
}
return ans;
}
signed main()
{
cin>>n>>m>>k;
for(int i=1;i<=n;i++) cin>>a[i];
for(int i=1;i<=n;i++)
for(int j=1;j<=n;j++)
if(i!=j) d[i][j]=1e18;
for(int i=1;i<=m;i++)
{
int a,b,c;
cin>>a>>b>>c;
d[a][b]=d[b][a]=min(d[a][b],c);
}
for(int k=1;k<=n;k++)
for(int i=1;i<=n;i++)
for(int j=1;j<=n;j++)
d[i][j]=min(d[i][j],d[i][k]+d[k][j]);
for(int k=1;k<=n;k++)
for(int i=1;i<=n;i++)
for(int j=i+1;j<=n;j++)
if(d[i][j]==d[i][k]+d[k][j]) cnt[k]++;
int ans=0;
for(int i=1;i<=n;i++) cnt[i]<<=1;
for(int i=1;i<=n;i++)
if(a[i]==0) ans=(ans+1-ksm(((n*(n-1))-cnt[i])*ksm(n*(n-1),mod-2)%mod,k)+mod)%mod;
else ans=(ans+1)%mod;
cout<<ans;
return 0;
}
C++(clang++11) 解法, 执行用时: 389ms, 内存消耗: 4044K, 提交时间: 2021-02-09 15:17:14
#include<bits/stdc++.h>
using namespace std;
const int mod=1023694381;
long long fastpow(long long a,int b)
{
long long s=1;
for(;b;b>>=1,a=a*a%mod)if(b&1)s=s*a%mod;
return s;
}
long long D[505][505];
int main()
{
int i,j,k,s,n,m,t,ans=0,inv;
bool V[505];
scanf("%d%d%d",&n,&m,&t);
inv=fastpow((long long)n*(n-1)%mod,mod-2);
for(i=1;i<=n;i++)
for(j=1;j<=n;j++)D[i][j]=1e18;
for(i=1;i<=n;i++)scanf("%d",&V[i]),ans+=V[i],D[i][i]=0;
while(m--)scanf("%d%d%d",&i,&j,&k),D[i][j]=D[j][i]=min(D[i][j],(long long)k);
for(k=1;k<=n;k++)
for(i=1;i<=n;i++)
for(j=1;j<=n;j++)D[i][j]=min(D[i][j],D[i][k]+D[k][j]);
for(k=1;k<=n;k++)
{
if(V[k])continue;
for(s=0,i=1;i<=n;i++)
for(j=1;j<=n;j++)if(i!=j&&D[i][j]==D[i][k]+D[k][j])s++;
ans=(ans+1-fastpow((1-(long long)s*inv%mod+mod)%mod,t)+mod)%mod;
}
printf("%d\n",ans);
return 0;
}