-
Notifications
You must be signed in to change notification settings - Fork 0
/
uva00388.cpp
82 lines (74 loc) · 1.88 KB
/
uva00388.cpp
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
#include <algorithm>
#include <bitset>
#include <cstring>
#include <climits>
#include <cmath>
#include <functional>
#include <iostream>
#include <iomanip>
#include <map>
#include <queue>
#include <stack>
#include <string>
#include <set>
#include <sstream>
#include <vector>
#define UNVISITED -1
#define _ ios_base::sync_with_stdio(0), cin.tie(0), cout.tie(0), cout.precision(15);
using namespace std;
typedef long long int64;
typedef pair<int, int> ii;
map<char, int> c2i;
vector<double> value;
vector<int> dist;
vector<char> source, planet;
vector<string> AdjList;
queue<char> Q;
void bfs(){
for(int i = 0; i < source.size(); ++i){
Q.push(source[i]);
dist[c2i[source[i]]] = 0;
}
char p, q; int id1, id2;
while(!Q.empty()){
p = Q.front(); Q.pop();
id1 = c2i[p];
for(int i = 0; i < AdjList[id1].size(); ++i){
q = AdjList[id1][i];
if(q == '*') continue;
id2 = c2i[q];
if(dist[id2] == UNVISITED){
dist[id2] = dist[id1] + 1;
Q.push(q);
}
}
}
}
int main(){ _
int n; char ch;
while(cin >> n){
c2i.clear();
source.clear();
value.assign(n, 0);
planet.assign(n, ' ');
dist.assign(n, UNVISITED);
AdjList.assign(n, "");
for(int i = 0; i < n; ++i){
cin >> planet[i] >> value[i] >> AdjList[i];
c2i[ch] = i;
for(int j = 0; j < AdjList[i].size(); ++j)
if(AdjList[i][j] == '*') source.push_back(ch);
}
bfs();
double ans = 0.0; int id = -1;
for(int i = 0; i < n; ++i){
value[i] = value[i] * pow(0.95, dist[i]);
if(value[i] > ans){
ans = value[i];
id = i;
}
}
cout << "Import from " << planet[id] << endl;
}
return 0;
}