关于一个图算法的应用

/**
 * 
 * @author SHQ
 *编程题 | 30分 1/2
 *题目描述：
	小A是一个城市中救援机构的负责人，他手头上有一张特殊的地图，记载了本省各个城市中救援队伍的数量和城市之间的道路连接情况。
	他的任务相当重要，除负责本市紧急情况救援外，他还需要在某个其他城市发生紧急情况时，第一时间带领他的队伍参与救援，
	同时调动路过城市的救援机构参与救援。
输入
	多组输入数据，第一行是一个正整数T(T<=10)，表示测试数据的组数，接下来包含T组测试数据。
	每组测试数据的第一行包含四个整数n(1


import java.util.*;

class Main{
    public static class Node{
        public int val;
        public int in;//入度
        public int out;//出度
        public ArrayList<Node> nexts;
        public ArrayList<Edge> edges;
        public Node(int val){
            this.val=val;
            in=0;
            out=0;
            nexts=new ArrayList<Node>();
            edges=new ArrayList<Edge>();
        }
    }
    public static class Edge{
        public int weight;
        public Node from;//入度
        public Node to;//出度
        public Edge(Node from,Node to,int weight){
            this.weight=weight;
            this.from=from;
            this.to=to;
        }
    }
    public static class Graph{
        public HashMap<Integer,Node> nodes;
        public HashSet<Edge> edges;
        public Graph(){
            nodes=new HashMap<Integer,Node>();
            edges=new HashSet<Edge>();
        }
    }
    //用一个二维数组来表示图，格式为: 权值 = matrix[0][0]  from点 = matrix[0][1]  to点 = matrix[0][2]
    public static void initGraph(int[][] matrix,Graph graph){
        for (int i=0;i<matrix.length;i++){
            int from=matrix[i][0];
            int to = matrix[i][1];
            int weight = matrix[i][2];

            if (!graph.nodes.containsKey(from)){
                graph.nodes.put(from,new Node(from));
            }
            if (!graph.nodes.containsKey(to)){
                graph.nodes.put(to,new Node(to));
            }
            Node fromNode = graph.nodes.get(from);
            Node toNode = graph.nodes.get(to);
            Edge edge = new Edge(fromNode,toNode,weight);
            fromNode.nexts.add(toNode);
            fromNode.out=fromNode.out+1;
            toNode.in=toNode.in+1;
            fromNode.edges.add(edge);
            graph.edges.add(edge);
        }
    }


    static int res=0;
    static int max=0;
    public static void main(String[] args){
        Scanner in = new Scanner(System.in);
        int n = in.nextInt();
        int m= in.nextInt();
        int s = in.nextInt();
        int t = in.nextInt();
        int[] savenums = new int[n];
        int[][] maxtire = new int[m][3];
        for (int i=0;i<n;i++){
            savenums[i] = in.nextInt();
        }
        for (int i=0;i<m;i++){
            maxtire[i][0]=in.nextInt();
            maxtire[i][1]=in.nextInt();
            maxtire[i][2]=in.nextInt();
        }
        Graph graph = new Graph();
        initGraph(maxtire,graph);
        Node start = graph.nodes.get(s);
        Node end = graph.nodes.get(t);
        dfs(start,end,0,savenums);
        System.out.println(res);
        System.out.println(max);

    }

    public static void  dfs(Node now,Node end,int sum,int[] savenums){
        if (now.val==end.val){
            max=Math.max(max,sum+savenums[now.val]);
            res=res+1;
            return ;
        }
        if (now.nexts==null){
            return;
        }
        for (Node next:now.nexts){
            dfs(next,end,sum+savenums[next.val],savenums);
        }

    }


}
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
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147