4172489_re.java

北大大牛代码 1240道题的原代码 超级权威

/*
 * To change this template, choose Tools | Templates
 * and open the template in the editor.
 */

//package poj1911;

import java.util.*;

/**
 *
 * @author ZhaoJian
 */
public class Main {
    private Scanner in;
    private int m, n, tot;
    private int [][]map = new int[500][500];
    private int[] dis = new int[500];
    private boolean[] used = new boolean[500];
    /**
     * @param args the command line arguments
     */
    public static void main(String[] args) {
        // TODO code application logic here
        new Main().run();
    }

    private void run() {
        in = new Scanner (System.in);
        
        while (true) {
            m = in.nextInt() + 1;
            n = in.nextInt() + 1;
            if (m == 1 && n == 1) {
                break;
            }
            tot = m * n;
            for (int i = 0; i < tot; i++) {
                Arrays.fill(map, 0);
            }
            int u, v;
            for (int i = 0; i < n - 1; i++) {
                int t;
                try {
                    t = 2520 / in.nextInt();
                } catch (Exception e) {
                    t = 0;
                }
                String dir = in.next();
                if (t == 0) {
                    continue;
                }
                u = i;v = i + 1;
                switch (dir.charAt(0)) {
                    case '*':   map[u][v] = map[v][u] = t;break;
                    case '<':   map[v][u] = t;break;
                    case '>':   map[u][v] = t;break;
                }
            }
            for (int i = 0; i < m - 1; i++) {
                for (int j = 0; j < n; j++) {
                    u = i * n + j;
                    v = u + n;
                    int t;
                    try {
                        t = 2520 / in.nextInt();
                    } catch (Exception e) {
                        t = 0;
                    }
                    String dir = in.next();
                    if (t == 0) {
                        continue;
                    }
                    switch (dir.charAt(0)) {
                        case '*':   map[u][v] = map[v][u] = t;break;
                        case '^':   map[v][u] = t;break;
                        case 'v':   map[u][v] = t;break;
                    }
                }
                for (int j = 0; j < n - 1; j++) {
                    u = (i + 1)* n + j;
                    v = u + 1;
                    int t;
                    try {
                        t = 2520 / in.nextInt();
                    } catch (Exception e) {
                        t = 0;
                    }
                    String dir = in.next();
                    if (t == 0) {
                        continue;
                    }
                    switch (dir.charAt(0)) {
                        case '*':   map[u][v] = map[v][u] = t;break;
                        case '<':   map[v][u] = t;break;
                        case '>':   map[u][v] = t;break;
                    }
                }
            }
            System.out.println(getShortestPath());
        }
    }
    
    private String getShortestPath() {
        
        Arrays.fill(dis, Integer.MAX_VALUE);
        Arrays.fill(used, true);
        dis[0] = 0;
        for (int i = 0; i < tot; i++) {
            int min = Integer.MAX_VALUE;
            int id = -1;
            
            for (int j = 0; !used[tot - 1] && j < tot; j++) {
                if (!used[j] && dis[j] < min) {
                    min = dis[j];
                    id = j;
                }
            }
            if (id == -1) {
                break;
            }
            used[id] = true;
            for (int j = 0; j < tot; j++) {
                if (!used[j] && map[id][j] != 0 && dis[id] + map[id][j] < dis[j]) {
                    dis[j] = dis[id] + map[id][j];
                }
            }
        }
        return used[tot - 1] ? Integer.toString(dis[tot - 1]) + " blips" : "Holiday";
    }
    
}