#C. 黑暗城堡
- 题意
设 D[i] 为第 i 号房间与第 1 号房间的最短路径长度;
S[i] 为实际修建的树形城堡中第 i 号房间与第 1 号房间的路径长度
要求对于所有整数 i ( 1<=i <=N ) ,有 S[i]=D[i] 成立的方案数
- 分析
跑一遍最短路,再\(N^2\)暴力每两个点之间的边
如果\(dis(1,j)=dis(1,i)+w(i,j)\),j的方案数+1
最后用乘法原理全部相乘即可
- 细节
勿忘mod
#include<bits/stdc++.h>
using namespace std;
#define ll long long
ll n,m,rep[2000005],dis[2000005],vis[2000005],lj[1005][1005];
ll head[2000005],tot;
ll mod=(1<<31)-1;
struct nood{
ll v;
ll w;
ll nxt;
}es[2000005];
void adde(ll u,ll v,ll w){
es[++tot].v=v,es[tot].w=w,es[tot].nxt=head[u],head[u]=tot;
}
void dij(){
memset(dis,0x3f,sizeof(dis));
dis[1]=0;
priority_queue<pair<ll,ll>,vector<pair<ll,ll> >,greater<pair<ll,ll> > >q;
q.push({0,1});//dis,编号
while(!q.empty()){
pair<ll,ll> vv=q.top();
q.pop();
ll di=vv.first;
ll bh=vv.second;
if(di==dis[bh]){
//cout<<bh<<"start:"<<endl;
for(int kk=head[bh];kk;kk=es[kk].nxt){
ll vvv=es[kk].v;
//cout<<vvv<<" for "<<dis[vvv]<<endl;
if(dis[vvv]>es[kk].w+di){
//cout<<vvv<<":::"<<es[kk].w<<"+"<<di<<endl;
dis[vvv]=es[kk].w+di;
q.push(make_pair(dis[vvv],vvv));
}
}
}
}
}
int main(){
cin>>n>>m;
ll x,y,z;
memset(lj,0x3f,sizeof(lj));
for(int i=1;i<=m;i++){
cin>>x>>y>>z;
//cout<<x<<" "<<y<<" "<<z<<endl;
adde(x,y,z);
adde(y,x,z);
lj[x][y]=lj[y][x]=min(lj[x][y],z);
}
dij();
ll ans=1;
for(int i=1;i<=n;i++){
//cout<<"dis i for"<<i<<":"<<dis[i]<<endl;
ll s=0;
for(int j=1;j<=n;j++){
if(dis[i]==dis[j]+lj[i][j]&&i!=j&&dis[i]!=0){
s++;
}
}
if(s!=0){
//cout<<s<<endl;
ans=(ans*s)%mod;
//cout<<ans<<endl;
ans%=mod;
}
}
cout<<ans;
}
标签:2000005,黑暗,di,城堡,ll,lj,vv,dis
From: https://www.cnblogs.com/Misty-post/p/18438316