Guest User

Untitled

a guest
Sep 12th, 2017
119
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1.         static class BlockProcessor extends AbstractQueryProcessor {
  2.            
  3.             static final int BLOCK_SIZE = 250;
  4.        
  5.             int blockSize;
  6.            
  7.             int blocksCount;
  8.             int[] blocks;
  9.            
  10.             int blockSideSize;
  11.             int[][] blockSideVertices;
  12.             int[] blockInnerIndexes;
  13.            
  14.             boolean[][] blockSideActive;
  15.            
  16.             boolean[][][] blockSidesPathContains;
  17.             long[][][] blockSidesPathDeltas;
  18.            
  19.             long[][][] blockSidesPathLengths;
  20.             boolean[][][] blockSidesPathInner;
  21.            
  22.             int[] blockGlobalVertices;
  23.             int[] blockGlobalIndexes;
  24.            
  25.             int blockGlobalGraphSize;
  26.             Edge[][] blockGlobalGraph;
  27.            
  28.             long[][] blockGlobalPathLengths;
  29.            
  30.             public BlockProcessor() {
  31.                 this(BLOCK_SIZE);
  32.             }
  33.            
  34.             public BlockProcessor(int blockSize) {
  35.                 this.blockSize = blockSize;
  36.             }
  37.            
  38.             @Override
  39.             void additionalInit() {
  40.                 this.blockSize = min(blockSize, n);
  41.                
  42.                 this.blocks = generateBlocks(m, n, size, vertices, blockSize);
  43.                 this.blocksCount = calculateBlocksCount(blocks);
  44.                
  45.                 this.blockSideSize = 2 * m;
  46.                
  47.                 this.blockSideVertices = generateBlockSideVertices(m, n, vertices, blocks, blocksCount, blockSideSize);
  48.                 this.blockInnerIndexes = generateBlockInnerIndexes(size, blockSideVertices);
  49.                
  50.                 prepareBlockSidesPaths();
  51.                 prepareBlockGlobalGraph();
  52.                 prepareBlockGlobalPaths();
  53.                
  54.                 initUpdates();
  55.             }
  56.            
  57.             void prepareBlockGlobalPaths() {
  58.                 this.blockGlobalPathLengths = new long[blockGlobalGraphSize][blockGlobalGraphSize];
  59.                
  60.                 final long[] distances = new long[blockGlobalGraphSize];
  61.                
  62.                 Queue<Vertex> queue = new PriorityQueue<Vertex>(blockGlobalGraphSize * (blockSideSize + 1));
  63.                
  64.                 int[] blockGlobalColorsSeen = new int[blockGlobalGraphSize];
  65.                 int[] blockGlobalColorsProcessed = new int[blockGlobalGraphSize];
  66.                 int blockGlobalColor = 1;
  67.                
  68.                 for (int start = 0; start < blockGlobalGraphSize; ++start) {
  69.                     ++blockGlobalColor;
  70.                     blockGlobalColorsSeen[start] = blockGlobalColor;
  71.                    
  72.                     distances[start] = 0;
  73.                     queue.add(new Vertex(start, distances[start]));
  74.                    
  75.                     while (queue.size() > 0) {
  76.                         Vertex v = queue.poll();
  77.                         int from = v.index;
  78.                         if (blockGlobalColorsProcessed[from] == blockGlobalColor) continue;
  79.                        
  80.                         long fromDistance = distances[from];
  81.                         for (Edge e : blockGlobalGraph[from]) {
  82.                             int to = e.to;
  83.                            
  84.                             if (blockGlobalColorsSeen[to] != blockGlobalColor) {
  85.                                 distances[to] = INF;
  86.                                 blockGlobalColorsSeen[to] = blockGlobalColor;
  87.                             }
  88.                            
  89.                             if (distances[to] > fromDistance + e.w) {
  90.                                 distances[to] = fromDistance + e.w;
  91.                                 queue.add(new Vertex(to, distances[to]));
  92.                             }
  93.                         }
  94.                        
  95.                         blockGlobalColorsProcessed[from] = blockGlobalColor;
  96.                     }
  97.                    
  98.                     for (int end = 0; end < blockGlobalGraphSize; ++end) {
  99.                         blockGlobalPathLengths[start][end] = distances[end];
  100.                     }
  101.                 }
  102.             }
  103.            
  104.             void prepareBlockGlobalGraph() {
  105.                 this.blockGlobalVertices = generateBlockGlobalVertices(blocksCount, blockSideSize, blockInnerIndexes);
  106.                 this.blockGlobalGraphSize = blockGlobalVertices.length;
  107.                
  108.                 this.blockGlobalIndexes = generateBlockGlobalIndexes(size, blockGlobalVertices);
  109.                
  110.                 List<Edge>[] blockGlobalEdgeLists = new List[blockGlobalGraphSize];
  111.                 for (int v = 0; v < blockGlobalGraphSize; ++v) {
  112.                     blockGlobalEdgeLists[v] = new ArrayList<Edge>();
  113.                 }
  114.                
  115.                 for (int i = 0; i < m; ++i) {
  116.                     for (int j = 1; j < n - 1; ++j) {
  117.                         int cur = vertices[i][j];
  118.                         int next = vertices[i][j + 1];
  119.                        
  120.                         int curBlock = blocks[cur], nextBlock = blocks[next];
  121.                         if (curBlock != nextBlock) {
  122.                             int curGlobalVertex = blockGlobalIndexes[cur], nextGlobalVertex = blockGlobalIndexes[next];
  123.                            
  124.                             long weight = right[i][j];
  125.                            
  126.                             blockGlobalEdgeLists[curGlobalVertex].add(new Edge(nextGlobalVertex, weight));
  127.                             blockGlobalEdgeLists[nextGlobalVertex].add(new Edge(curGlobalVertex, weight));
  128.                         }
  129.                     }
  130.                 }
  131.                
  132.                 for (int block = 0; block < blocksCount; ++block) {
  133.                     for (int i = 0; i < blockSideSize; ++i) {
  134.                         if (!blockSideActive[block][i]) continue;
  135.                        
  136.                         int from = blockSideVertices[block][i];
  137.                         int fromGlobalVertex = blockGlobalIndexes[from];
  138.                        
  139.                         for (int j = 0; j < blockSideSize; ++j) {
  140.                             if (!blockSideActive[block][j]) continue;
  141.                            
  142.                             int to = blockSideVertices[block][j];
  143.                             if (from == to) continue;
  144.                            
  145.                             int toGlobalVertex = blockGlobalIndexes[to];
  146.                             long weight = blockSidesPathLengths[block][i][j];
  147.                            
  148.                             blockGlobalEdgeLists[fromGlobalVertex].add(new Edge(toGlobalVertex, weight));
  149.                         }
  150.                     }
  151.                 }
  152.                
  153.                 this.blockGlobalGraph = new Edge[blockGlobalGraphSize][];
  154.                 for (int v = 0; v < blockGlobalGraphSize; ++v) {
  155.                     blockGlobalGraph[v] = blockGlobalEdgeLists[v].toArray(new Edge[0]);
  156.                 }
  157.             }
  158.            
  159.             void prepareBlockSidesPaths() {
  160.                 this.blockSideActive = new boolean[blocksCount][blockSideSize];
  161.                 for (int v = 0; v < size; ++v) {
  162.                     int block = blocks[v];
  163.                     int sideIndex = blockInnerIndexes[v];
  164.                     if (sideIndex != -1) {
  165.                         blockSideActive[block][sideIndex] = true;
  166.                     }
  167.                 }
  168.                
  169.                 this.blockSidesPathDeltas = new long[blocksCount][blockSideSize][blockSideSize];
  170.                
  171.                 this.blockSidesPathContains = new boolean[blockSideSize][blockSideSize][size];
  172.                 this.blockSidesPathLengths = new long[blocksCount][blockSideSize][blockSideSize];
  173.                 this.blockSidesPathInner = new boolean[blocksCount][blockSideSize][blockSideSize];
  174.                
  175.                 blockInnerDijkstraInit();
  176.                
  177.                 for (int block = 0; block < blocksCount; ++block) {
  178.                     int[] blockSide = blockSideVertices[block];
  179.                    
  180.                     for (int start : blockSide) {
  181.                         int blockInnerIndexStart = blockInnerIndexes[start];
  182.                        
  183.                         blockInnerDijkstra(start, START_MODE);
  184.                        
  185.                         for (int end : blockSide) {
  186.                             int blockInnerIndexEnd = blockInnerIndexes[end];
  187.                            
  188.                             blockSidesPathInner[block][blockInnerIndexStart][blockInnerIndexEnd] = (start != end);
  189.                            
  190.                             for (int cur = end; cur != -1; cur = modeParents[START_MODE][cur]) {
  191.                                
  192.                                 if (blockInnerIndexes[cur] != -1) {
  193.                                     if (cur != end && cur != start) {
  194.                                         blockSidesPathInner[block][blockInnerIndexStart][blockInnerIndexEnd] = false;
  195.                                         break;
  196.                                     }
  197.                                 }
  198.                             }
  199.                            
  200.                             blockSidesPathDeltas[block][blockInnerIndexStart][blockInnerIndexEnd] = 0;
  201.                            
  202.                             if (blockSidesPathInner[block][blockInnerIndexStart][blockInnerIndexEnd]) {
  203.                                 blockSidesPathLengths[block][blockInnerIndexStart][blockInnerIndexEnd] = modeDistances[START_MODE][end];
  204.                                
  205.                                 for (int cur = end; cur != -1; cur = modeParents[START_MODE][cur]) {
  206.                                     if (blockInnerIndexes[cur] != -1) continue;
  207.                                    
  208.                                     // we only need really inner vertices
  209.                                     blockSidesPathContains[blockInnerIndexStart][blockInnerIndexEnd][cur] = true;
  210.                                 }  
  211.                             } else {
  212.                                 blockSidesPathLengths[block][blockInnerIndexStart][blockInnerIndexEnd] = INF;
  213.                             }
  214.                         }
  215.                     }
  216.                 }
  217.             }
  218.            
  219.             final int START_MODE = 0, END_MODE = 1;
  220.            
  221.             long[][] modeDistances;
  222.             int[][] modeParents;
  223.            
  224.             int[] colorsSeen;
  225.             int[] colorsProcessed;
  226.             int curColor;
  227.            
  228.             Queue<Vertex>[] modeQueues;
  229.            
  230.             final long INF = Long.MAX_VALUE / 2;
  231.            
  232.             class Vertex implements Comparable<Vertex> {
  233.                 int index;
  234.                 long distance;
  235.                 public Vertex(int index, long distance) {
  236.                     super();
  237.                     this.index = index;
  238.                     this.distance = distance;
  239.                 }
  240.                 @Override
  241.                 public int compareTo(Vertex other) {
  242.                     long iDistance = distance, jDistance = other.distance;
  243.                     return (iDistance < jDistance) ? -1 : ((iDistance > jDistance) ? 1 : 0);
  244.                 }
  245.             }
  246.            
  247.             void blockInnerDijkstraInit() {
  248.                 this.modeDistances = new long[2][size];
  249.                 this.modeParents = new int[2][size];
  250.                
  251.                 this.colorsSeen = new int[size];
  252.                 this.colorsProcessed = new int[size];
  253.                 this.curColor = 1;
  254.                
  255.                 this.modeQueues = new Queue[2];
  256.                 for (int i = 0; i < 2; ++i) {
  257.                     final int mode = i;
  258.                     modeQueues[mode] = new PriorityQueue<Vertex>(size);
  259.                 }
  260.             }
  261.            
  262.             void blockInnerDijkstra(int start, int mode) {
  263.                 int block = blocks[start];
  264.                
  265.                 ++curColor;
  266.                 colorsSeen[start] = curColor;
  267.                
  268.                 long[] distances = modeDistances[mode];
  269.                 distances[start] = 0;
  270.                
  271.                 int[] parents = modeParents[mode];
  272.                 parents[start] = -1;
  273.                
  274.                 Queue<Vertex> queue = modeQueues[mode];
  275.                 queue.add(new Vertex(start, 0));
  276.                
  277.                 while (queue.size() > 0) {
  278.                     Vertex v = queue.poll();
  279.                     if (colorsProcessed[v.index] == curColor) continue;
  280.                    
  281.                     int from = v.index;
  282.                     long fromDistance = distances[from];
  283.                     for (Edge e : graph[from]) {
  284.                         int to = e.to;
  285.                         if (blocks[to] != block) continue;
  286.                        
  287.                         if (colorsSeen[to] != curColor) {
  288.                             distances[to] = INF;
  289.                             parents[to] = -1;
  290.                             colorsSeen[to] = curColor;
  291.                         }
  292.                        
  293.                         if (distances[to] > fromDistance + e.w) {
  294.                             distances[to] = fromDistance + e.w;
  295.                             parents[to] = from;
  296.                             queue.add(new Vertex(to, distances[to]));
  297.                         }
  298.                     }
  299.                    
  300.                     colorsProcessed[from] = curColor;
  301.                 }
  302.             }
  303.            
  304.             int[] updateColors;
  305.             int updateCurColor;
  306.            
  307.             void initUpdates() {
  308.                 this.updateColors = new int[size];
  309.                 this.updateCurColor = 1;
  310.             }
  311.            
  312.             @Override
  313.             void updatePath(int start, int end, long delta) {
  314.                 ++updateCurColor;
  315.                
  316.                 blockInnerDijkstra(start, START_MODE);
  317.                 blockInnerDijkstra(end, END_MODE);
  318.                
  319.                 int startBlock = blocks[start], endBlock = blocks[end];
  320.                
  321.                 long startEndLength = INF;
  322.                 int startOptimalSide = -1, endOptimalSide = -1;
  323.                 if (startBlock == endBlock) {
  324.                     startEndLength = modeDistances[START_MODE][end];
  325.                 }
  326.                
  327.                 for (int startSide = 0; startSide < blockSideSize; ++startSide) {
  328.                     if (!blockSideActive[startBlock][startSide]) continue;
  329.                    
  330.                     int startSideVertex = blockSideVertices[startBlock][startSide];
  331.                     long startSideDistance = modeDistances[START_MODE][startSideVertex];
  332.                    
  333.                     int startSideGlobalVertex = blockGlobalIndexes[startSideVertex];
  334.                    
  335.                     for (int endSide = 0; endSide < blockSideSize; ++endSide) {
  336.                         if (!blockSideActive[endBlock][endSide]) continue;
  337.                        
  338.                         int endSideVertex = blockSideVertices[endBlock][endSide];
  339.                         long endSideDistance = modeDistances[END_MODE][endSideVertex];
  340.                        
  341.                         int endSideGlobalVertex = blockGlobalIndexes[endSideVertex];
  342.                        
  343.                         long startEndSideDistance = startSideDistance + blockGlobalPathLengths[startSideGlobalVertex][endSideGlobalVertex] + endSideDistance;
  344.                         if (startEndSideDistance < startEndLength) {
  345.                             startEndLength = startEndSideDistance;
  346.                             startOptimalSide = startSide;
  347.                             endOptimalSide = endSide;
  348.                         }
  349.                     }
  350.                 }
  351.                
  352.                 if (startOptimalSide == -1 || endOptimalSide == -1) {
  353.                     // inner path
  354.                     for (int cur = end; cur != -1; cur = modeParents[START_MODE][cur]) {
  355.                         vertexValues[cur] += delta;
  356.                     }
  357.                 } else {
  358.                     int startOptimalVertex = blockSideVertices[startBlock][startOptimalSide];
  359.                     int startOptimalGlobalVertex = blockGlobalIndexes[startOptimalVertex];
  360.                    
  361.                     int endOptimalVertex = blockSideVertices[endBlock][endOptimalSide];
  362.                     int endOptimalGlobalVertex = blockGlobalIndexes[endOptimalVertex];
  363.                    
  364.                     for (int cur = startOptimalVertex; cur != -1; cur = modeParents[START_MODE][cur]) {
  365.                         if (updateColors[cur] == updateCurColor) continue;
  366.                         vertexValues[cur] += delta;
  367.                         updateColors[cur] = updateCurColor;
  368.                     }
  369.                    
  370.                     for (int cur = endOptimalVertex; cur != -1; cur = modeParents[END_MODE][cur]) {
  371.                         if (updateColors[cur] == updateCurColor) continue;
  372.                         vertexValues[cur] += delta;
  373.                         updateColors[cur] = updateCurColor;
  374.                     }
  375.                    
  376.                     long startEndGlobalDistance = blockGlobalPathLengths[startOptimalGlobalVertex][endOptimalGlobalVertex];
  377.                    
  378.                     for (int block = 0; block < blocksCount; ++block) {
  379.                         for (int startSide = 0; startSide < blockSideSize; ++startSide) {
  380.                             if (!blockSideActive[block][startSide]) continue;
  381.                            
  382.                             int startVertex = blockSideVertices[block][startSide];
  383.                             int startGlobalVertex = blockGlobalIndexes[startVertex];
  384.                            
  385.                             long startGlobalDistance = blockGlobalPathLengths[startOptimalGlobalVertex][startGlobalVertex];
  386.                            
  387.                             for (int endSide = 0; endSide < blockSideSize; ++endSide) {
  388.                                 if (!blockSideActive[block][endSide]) continue;
  389.                                
  390.                                 if (!blockSidesPathInner[block][startSide][endSide]) continue;
  391.                                
  392.                                 int endVertex = blockSideVertices[block][endSide];
  393.                                 int endGlobalVertex = blockGlobalIndexes[endVertex];
  394.                                
  395.                                 long endGlobalDistance = blockGlobalPathLengths[endGlobalVertex][endOptimalGlobalVertex];
  396.                                
  397.                                 long startEndInnerDistance = blockSidesPathLengths[block][startSide][endSide];///[startGlobalVertex][endGlobalVertex];
  398.                                 if (startGlobalDistance + startEndInnerDistance + endGlobalDistance == startEndGlobalDistance) {
  399.                                     blockSidesPathDeltas[block][startSide][endSide] += delta;
  400.                                    
  401.                                     if (updateColors[startVertex] != updateCurColor) {
  402.                                         updateColors[startVertex] = updateCurColor;
  403.                                         vertexValues[startVertex] += delta;
  404.                                     }
  405.                                    
  406.                                     if (updateColors[endVertex] != updateCurColor) {
  407.                                         updateColors[endVertex] = updateCurColor;
  408.                                         vertexValues[endVertex] += delta;
  409.                                     }
  410.                                 }
  411.                             }
  412.                         }
  413.                     }
  414.                    
  415.                    
  416.                 }
  417.             }
  418.            
  419.             @Override
  420.             long getVertexValue(int v) {
  421.                 long value = 0;
  422.                
  423.                 int block = blocks[v];
  424.                 for (int start = 0; start < blockSideSize; ++start) {
  425.                     for (int end = 0; end < blockSideSize; ++end) {
  426.                         if (blockSidesPathInner[block][start][end] && blockSidesPathContains[start][end][v]) {
  427.                             value += blockSidesPathDeltas[block][start][end];
  428.                         }
  429.                     }
  430.                 }
  431.                
  432.                 return value;
  433.             }
  434.         }
  435.        
  436.         static int[] generateBlockGlobalIndexes(int size, int[] blockGlobalVertices) {
  437.             int[] blockGlobalIndexes = new int[size];
  438.             Arrays.fill(blockGlobalIndexes, -1);
  439.            
  440.             for (int index = 0; index < blockGlobalVertices.length; ++index) {
  441.                 blockGlobalIndexes[blockGlobalVertices[index]] = index;
  442.             }
  443.            
  444.             return blockGlobalIndexes;
  445.         }
  446.         static int[] generateBlockGlobalVertices(int blocksCount, int blockSideSize, int[] blockInnerIndexes) {
  447.             List<Integer> blockGlobalVertices = new ArrayList<Integer>();
  448.            
  449.             for (int v = 0; v < blockInnerIndexes.length; ++v) {
  450.                 if (blockInnerIndexes[v] != -1) {
  451.                     blockGlobalVertices.add(v);
  452.                 }
  453.             }
  454.            
  455.             return castInt(blockGlobalVertices);
  456.         }
  457.         static int[] generateBlockInnerIndexes(int size, int[][] blockSideVertices) {
  458.             int[] blockInnerIndexes = new int[size];
  459.             Arrays.fill(blockInnerIndexes, -1);
  460.            
  461.             for (int[] blockSide : blockSideVertices) {
  462.                 for (int index = 0; index < blockSide.length; ++index) {
  463.                     blockInnerIndexes[blockSide[index]] = index;
  464.                 }
  465.             }
  466.            
  467.             return blockInnerIndexes;
  468.         }
  469.        
  470.         static int[][] generateBlockSideVertices(int m, int n, int[][] vertices, int[] blocks, int blocksCount, int blockSideSize) {
  471.             int[][] blockSideVertices = new int[blocksCount][blockSideSize];
  472.             int[] blockSizes = new int[blocksCount];
  473.            
  474.             for (int i = 0; i < m; ++i) {
  475.                 for (int j = 0; j < n; ++j) {
  476.                     int cur = vertices[i][j];
  477.                     int curBlock = blocks[cur];
  478.                    
  479.                     if (j == 0 || j == n - 1) {
  480.                         blockSideVertices[curBlock][blockSizes[curBlock]++] = cur;
  481.                        
  482.                         // it is more comfortable to have block sides of length 6 every time, even when n == 1
  483.                         if (n - 1 == 0) {
  484.                             blockSideVertices[curBlock][blockSizes[curBlock]++] = cur; 
  485.                         }
  486.                     } else {
  487.                         int next = vertices[i][j + 1];
  488.                        
  489.                         int nextBlock = blocks[next];
  490.                         if (curBlock != nextBlock) {
  491.                             blockSideVertices[curBlock][blockSizes[curBlock]++] = cur;
  492.                             blockSideVertices[nextBlock][blockSizes[nextBlock]++] = next;
  493.                         }  
  494.                     }
  495.                 }
  496.             }
  497.            
  498.             return blockSideVertices;
  499.         }
  500.        
  501.         static int[] generateBlocks(int m, int n, int size, int[][] vertices, int blockSize) {
  502.             int[] blocks = new int[size];
  503.            
  504.             for (int i = 0; i < m; ++i) {
  505.                 for (int j = 0; j < n; ++j) {
  506.                     int v = vertices[i][j];
  507.                     blocks[v] = j / blockSize;
  508.                 }
  509.             }
  510.            
  511.             return blocks;
  512.         }
  513.        
  514.         static int calculateBlocksCount(int[] blocks) {
  515.             return getMinMax(blocks).y + 1;
  516.         }
  517.        
  518.         interface QueryProcessor {
  519.            
  520.             QueryProcessor init(int m, int n, long[][] down, long[][] right);
  521.            
  522.             void update(int i1, int j1, int i2, int j2, long delta);
  523.             long get(int i, int j);
  524.         }
  525.        
  526.         static abstract class AbstractQueryProcessor implements QueryProcessor {
  527.            
  528.             int m, n;
  529.             long[][] down;
  530.             long[][] right;
  531.            
  532.             int size;
  533.             int[][] vertices;
  534.            
  535.             Edge[][] graph;
  536.            
  537.             long[] vertexValues;
  538.            
  539.             @Override
  540.             public QueryProcessor init(int m, int n, long[][] down, long[][] right) {
  541.                 this.m = m;
  542.                 this.n = n;
  543.                
  544.                 this.down = down;
  545.                 this.right = right;
  546.      
  547.                 this.size = m * n;
  548.                 this.vertices = generateIndexes(m, n);
  549.                 this.graph = generateMatrixGraph(m, n, size, vertices, down, right);
  550.                
  551.                 this.vertexValues = new long[size];
  552.                
  553.                 additionalInit();
  554.                
  555.                 return this;
  556.             }
  557.            
  558.             abstract void additionalInit();
  559.            
  560.             @Override
  561.             public void update(int i1, int j1, int i2, int j2, long delta) {
  562.                 updatePath(vertices[i1][j1], vertices[i2][j2], delta);
  563.             }
  564.            
  565.             abstract void updatePath(int from, int to, long delta);
  566.            
  567.             @Override
  568.             public long get(int i, int j) {
  569.                 int v = vertices[i][j];
  570.                 return vertexValues[v] + getVertexValue(v);
  571.             }
  572.            
  573.             abstract long getVertexValue(int v);
  574.         }
  575.        
  576.        
  577.         static int[][] generateIndexes(int m, int n) {
  578.             int[][] indexes = new int[m][n];
  579.             for (int i = 0, index = 0; i < m; ++i) {
  580.                 for (int j = 0; j < n; ++j, ++index) {
  581.                     indexes[i][j] = index;
  582.                 }
  583.             }
  584.            
  585.             return indexes;
  586.         }
  587.        
  588.        
  589.         static Edge[][] generateMatrixGraph(int m, int n, int size, int[][] vertices, long[][] down, long[][] right) {
  590.             List<Edge>[] edgeLists = new List[size];
  591.             for (int v = 0; v < size; ++v) {
  592.                 edgeLists[v] = new ArrayList<Edge>();
  593.             }
  594.            
  595.             for (int i = 0; i < m - 1; ++i) {
  596.                 for (int j = 0; j < n; ++j) {
  597.                     int from = vertices[i][j];
  598.                     int to = vertices[i + 1][j];
  599.                    
  600.                     long weight = down[i][j];
  601.                    
  602.                     edgeLists[from].add(new Edge(to, weight));
  603.                     edgeLists[to].add(new Edge(from, weight));
  604.                 }
  605.             }
  606.            
  607.             for (int i = 0; i < m; ++i) {
  608.                 for (int j = 0; j < n - 1; ++j) {
  609.                     int from = vertices[i][j];
  610.                     int to = vertices[i][j + 1];
  611.                    
  612.                     long weight = right[i][j];
  613.                    
  614.                     edgeLists[from].add(new Edge(to, weight));
  615.                     edgeLists[to].add(new Edge(from, weight));
  616.                 }
  617.             }
  618.            
  619.             Edge[][] graph = new Edge[size][];
  620.             for (int v = 0; v < size; ++v) {
  621.                 graph[v] = edgeLists[v].toArray(new Edge[0]);
  622.             }
  623.            
  624.             return graph;
  625.         }
RAW Paste Data