1106. Lowest Price in Supply Chain 解析

本文主要是介绍1106. Lowest Price in Supply Chain 解析，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

是一个求最短链的问题，后面一个输出的是最短链的条数。

#include <iostream>
#include <vector>
#include <map>
#include <cstring>
#include <climits>#define MAX 100010using namespace std;int n;
double p, r;vector <int> chain[MAX];
map <int, bool> isRetailer;
int StoreCount = 0;
int min_depth = INT_MAX;void DFS(int u,int depth) {//u当前访问结点if (isRetailer[u]) {if (depth < min_depth) {min_depth = depth;StoreCount = 1;}else if (depth == min_depth) {StoreCount++;}return;}for (int i = 0; i < chain[u].size(); i++) {int v = chain[u][i];DFS(v, depth + 1);}
}int main() {cin >> n >> p >> r;int size;for (int i = 0; i < n; i++) {cin >> size;if (size == 0) {isRetailer[i] = true;}else {int temp;for (int j = 0; j < size; j++) {scanf("%d", &temp);chain[i].push_back(temp);}}}DFS(0,0);double price = p;for (int i = 0; i < min_depth; i++) {price *= (1 + r/100);}printf("%.04lf %d\n", price, StoreCount);return 0;}

这篇关于1106. Lowest Price in Supply Chain 解析的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---