首页 > 代码库 > PAT 1079

PAT 1079

2024-07-31 22:23:36   219人阅读

傻逼题...

PAT的出题我一直很想吐槽，数据之类的不是很灵，该给过不过，不该过随意过。

这道题需要全员double才能过，需要注意的是如果在float后面加上f也是过不了的... 变量都是double接着了还是过不了是为什么，感觉好奇怪，有可能是二进制表达的关系，大数据有凑巧是0.5或者是0.25的所以改成double但是没改0.01后面的f结果就过了的...

 

简单BFS

 1 #include <vector> 2 #include <iostream> 3 #include <queue> 4 #include <iomanip> 5  6 using namespace std; 7  8 double bfs(const vector<vector<int> > &graph, const double p, const double r){ 9     double p_fac = (double)(1.0 + r * 0.01);10     double cur_price = p;11     double res = 0.0f;12 13     queue<int> cur_level;14     cur_level.push(0);15     while (!cur_level.empty()){16         queue<int> next_level;17 18         while (!cur_level.empty()){19             int cur_idx = cur_level.front();20             cur_level.pop();21 22             int size = graph[cur_idx][0];23             if (size == 0){24                 res += graph[cur_idx][1] * cur_price;25             } else {26                 for (int i = 1; i < size + 1; i++){27                     next_level.push(graph[cur_idx][i]);28                 }29             }30         }31 32         cur_price *= p_fac;33         cur_level = next_level;34     }35 36     return res;37 }38 39 int main(){40     int N;41     double P, r;42 43     cin >> N >> P >> r;44 45     vector<vector<int> > graph(N, vector<int>());46     for (int i = 0; i < N; i++){47         int cnt, num;48         cin >> cnt;49         graph[i].push_back(cnt);50 51         if (cnt == 0){52             cin >> num;53             graph[i].push_back(num);54         } else {55             for (int j = 0; j < cnt; j++){56                 cin >> num;57                 graph[i].push_back(num);58             }59         }60     }61 62     double res = bfs(graph, P, r);63 64     cout << fixed << setprecision(1) << res << endl;65 66     return 0;67 }

 

PAT 1079


联系
我们