|
| 1 | +classSolution { |
| 2 | +funcalcEquation(equations:List<List<String>>,values:DoubleArray,queries:List<List<String>>):DoubleArray { |
| 3 | +val adj=HashMap<String,ArrayList<Pair<String,Double>>>().apply { |
| 4 | +for (iin equations.indices) { |
| 5 | +val (a, b)= equations[i] |
| 6 | +val value= values[i] |
| 7 | +this[a]= getOrDefault(a,arrayListOf()).apply { add(b to value) } |
| 8 | +this[b]= getOrDefault(b,arrayListOf()).apply { add(a to (1.0/ value)) } |
| 9 | + } |
| 10 | + } |
| 11 | + |
| 12 | +funbfs( |
| 13 | +start:String, |
| 14 | +end:String |
| 15 | + ):Double { |
| 16 | +if (start!in adj|| end!in adj) |
| 17 | +return-1.0 |
| 18 | + |
| 19 | +val visit=HashSet<String>() |
| 20 | +with (LinkedList<Pair<String,Double>>()) { |
| 21 | + addLast(start to1.0) |
| 22 | + visit.add(start) |
| 23 | + |
| 24 | +while (isNotEmpty()) { |
| 25 | +val (cur, totVal)= removeFirst() |
| 26 | + |
| 27 | +if (cur== end)return totVal |
| 28 | + |
| 29 | + adj[cur]?.forEach { |
| 30 | +val (next, nextVal)= it |
| 31 | +if (next!in visit) { |
| 32 | + addLast(next to (totVal* nextVal)) |
| 33 | + visit.add(next) |
| 34 | + } |
| 35 | + } |
| 36 | + } |
| 37 | + } |
| 38 | + |
| 39 | +return-1.0 |
| 40 | + } |
| 41 | + |
| 42 | +val res=DoubleArray(queries.size) |
| 43 | +for (iin queries.indices) { |
| 44 | +val (a, b)= queries[i] |
| 45 | + res[i]= bfs(a, b) |
| 46 | + } |
| 47 | + |
| 48 | +return res |
| 49 | + } |
| 50 | +} |