java算法

Question

题目如下：
The number of different path from C to C with duration of less than 30. In the sample data, the paths are: CDC, CEBC, CEBCDC, CDCEBC, CDEBC, CEBCEBC, CEBCEBCEBC.

Graph: AB5, BC4, CD8, DC8, DE6, AD5, CE2, EB3, AE7

题目意思大致是求出 C to C 在 长度在不超过30范围内共有过少条路径？

Answer 1

题目没有给出数据范围，如果数据比较小的话，在每个点上挂一张表，表示从C到该点有哪些路径长度可行，然后从C开始做一遍BFS即可，最后统计C点上表的大小即可。如果数据比较大可以考虑Tarjan缩环啥的……

Answer 2

private static class Pair{&nbsp; &nbsp; char c;&nbsp; &nbsp; int duration;&nbsp; &nbsp; public Pair(char c, int duration) {&nbsp; &nbsp; &nbsp; &nbsp; this.c = c;&nbsp; &nbsp; &nbsp; &nbsp; this.duration = duration;&nbsp; &nbsp; }}public int search(String[] input){&nbsp; &nbsp; Map<Character, Set<Pair>> map = new HashMap<>();&nbsp; &nbsp; for(String s: input){&nbsp; &nbsp; &nbsp; &nbsp; char c1 = s.charAt(0), c2 = s.charAt(1);&nbsp; &nbsp; &nbsp; &nbsp; int duration = s.charAt(2) - '0';&nbsp; &nbsp; &nbsp; &nbsp; if(!map.containsKey(c1))&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; map.put(c1, new HashSet<>());&nbsp; &nbsp; &nbsp; &nbsp; map.get(c1).add(new Pair(c2, duration));&nbsp; &nbsp; }&nbsp; &nbsp; int count = 0;&nbsp; &nbsp; Queue<Pair> q = new LinkedList<Pair>();&nbsp; &nbsp; q.offer(new Pair('C', 0));&nbsp; &nbsp; while(!q.isEmpty()){&nbsp; &nbsp; &nbsp; &nbsp; int size = q.size();&nbsp; &nbsp; &nbsp; &nbsp; while(size-- > 0){&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; Pair cur = q.poll();&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; for(Pair p: map.get(cur.c)){&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; if(cur.duration + p.duration >= 30)&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; continue;&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; if(p.c == 'C')&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; count++;&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; q.offer(new Pair(p.c, cur.duration + p.duration));&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; }&nbsp; &nbsp; &nbsp; &nbsp; }&nbsp; &nbsp; }&nbsp; &nbsp; return count;}@Testpublic void test(){&nbsp; &nbsp; assertEquals(7, search(new String[]{"AB5", "BC4", "CD8", "DC8", "DE6",&nbsp;&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; "AD5", "CE2", "EB3", "AE7"}));}