1 Star 0 Fork 0

hsmath/PAT advanced

加入 Gitee
与超过 1200万 开发者一起发现、参与优秀开源项目,私有仓库也完全免费 :)
免费加入
文件
克隆/下载
1106.cpp 1.24 KB
一键复制 编辑 原始数据 按行查看 历史
hsmath 提交于 2021-05-09 22:51 . 1106
/**
* @file 1106.cpp
* @author Shuang Hu <hsmath@ubuntu>
* @date Sun May 9 22:29:58 2021
*
* @brief PAT 1106
*
*
*/
#include<iomanip>
#include<iostream>
#include<vector>
#include<cmath>
using namespace std;
class Graph{
private:
vector<vector<int>> AdjMat;
int nodenum;
double price;
double rate;
int pathnum;
int minheight;
public:
Graph();
void DFS(int node,int height);//Deep-First-Search
void printinfo(){
double p;
p=price*pow(1+rate*1.0/100,minheight);
cout<<fixed<<setprecision(4)<<p<<" "<<pathnum<<endl;
}
};
Graph::Graph(){
int N;
double r1,r2;
cin>>N>>r1>>r2;
nodenum=N;
price=r1;
rate=r2;
for(int i=0;i<N;i++){
vector<int> adj;
int num;
cin>>num;
for(int j=0;j<num;j++){
int adjnode;
cin>>adjnode;
adj.push_back(adjnode);
}
AdjMat.push_back(adj);
}
pathnum=0;
minheight=100000;
}
void Graph::DFS(int node,int height){
if(AdjMat[node].size()==0){//Leaf
if(height<minheight){
minheight=height;
pathnum=1;
}else if(height==minheight){
pathnum++;
}
return;
}
for(int i=0;i<AdjMat[node].size();i++){
DFS(AdjMat[node][i],height+1);
}
return;
}
int main(){
Graph G;
G.DFS(0,0);
G.printinfo();
}
Loading...
马建仓 AI 助手
尝试更多
代码解读
代码找茬
代码优化
C++
1
https://gitee.com/hsmath/pat-advanced.git
git@gitee.com:hsmath/pat-advanced.git
hsmath
pat-advanced
PAT advanced
master

搜索帮助