AcWing 1596. 供应链最低价格
原题链接
简单
作者:
trafal
,
2021-04-05 16:46:28
,
所有人可见
,
阅读 409
#include<iostream>
#include<cstring>
#include<queue>
#include<unordered_map>
#include<cmath>
using namespace std;
const int N = 100010;
int n;
double p,r;
int dist[N];
int e[N],ne[N],idx,h[N];
unordered_map<int,int> mm;
void add(int a,int b)
{
e[idx] = b;
ne[idx] = h[a];
h[a] = idx++;
}
int main()
{
cin>>n>>p>>r;
memset(h,-1,sizeof h);
for(int i=0;i<n;i++)
{
int ki;
cin>>ki;
if(ki==0)
{
mm[i] = 0;
}
else
while(ki--)
{
int x;
cin>>x;
add(i,x);
}
}
dist[0] = 0;
queue<int> q;
q.push(0);
while(q.size())
{
int t = q.front();
q.pop();
for(int i=h[t];i!=-1;i=ne[i])
{
int j=e[i];
dist[j] = 1+dist[t];
q.push(j);
}
}
unordered_map<double,int> ps;
for(auto e:mm)
{
int k = e.first;
double pri = p*pow((1+r/100),dist[k]);
ps[pri]++;
}
double res = 1e10;
for(auto e:ps)
{
if(e.first<res) res = e.first;
}
printf("%.4f %d\n",res,ps[res]);
return 0;
}