首页 > 专题系列 > Java解POJ > POJ 3268 Silver Cow Party [解题报告] Java
2013
11-12

POJ 3268 Silver Cow Party [解题报告] Java

Silver Cow Party

问题描述 :

One cow from each of N farms (1 ≤ N ≤ 1000) conveniently numbered 1..N is going to attend the big cow party to be held at farm #X (1 ≤ XN). A total of M (1 ≤ M ≤ 100,000) unidirectional (one-way roads connects pairs of farms; road i requires Ti (1 ≤ Ti ≤ 100) units of time to traverse.

Each cow must walk to the party and, when the party is over, return to her farm. Each cow is lazy and thus picks an optimal route with the shortest time. A cow’s return route might be different from her original route to the party since roads are one-way.

Of all the cows, what is the longest amount of time a cow must spend walking to the party and back?

输入:

Line 1: Three space-separated integers, respectively: N, M, and X

Lines 2..M+1: Line i+1 describes road i with three space-separated integers: Ai, Bi, and Ti. The described road runs from farm Ai to farm Bi, requiring Ti time units to traverse.

输出:

Line 1: One integer: the maximum of time any one cow must walk.

样例输入:

4 8 2
1 2 4
1 3 2
1 4 7
2 1 1
2 3 5
3 1 2
3 4 4
4 2 3

样例输出:

10

温馨提示:

Cow 4 proceeds directly to the party (3 units) and returns via farms 1 and 3 (7 units), for a total of 10 time units.

解题代码:

import java.util.Arrays;
import java.util.Scanner; 

public class Main { 

 public static void main(String[] args) { 

         Scanner sc = new Scanner(System.in);
         int n = sc.nextInt();
         int m = sc.nextInt();
         int x = sc.nextInt();
         int[][] map1 = new int[n + 1][n + 1];
         int[][] map2 = new int[n + 1][n + 1];

         boolean[] visted = new boolean[n + 1];
         int[] dist1 = new int[n + 1];
         int[] dist2 = new int[n + 1];

         for (int i = 0; i < m; i++) {
             int a = sc.nextInt();
             int b = sc.nextInt();
             int t = sc.nextInt();
             map1[a][b] = t;
             map2[b][a] = t;
        } 

        dijkstra(visted, dist1, map1, x); 

        dijkstra(visted, dist2, map2, x); 

        int max = Integer.MIN_VALUE; 

        for (int i = 1; i <= n; i++) {
           if (dist1[i] + dist2[i] > max) {
               max = dist1[i] + dist2[i];
          }
       } 

       System.out.println(max);
 } 

 public static void dijkstra(boolean[] visted, int[] dist, int[][] map, int x) {
     Arrays.fill(visted, false);
     Arrays.fill(dist, Integer.MAX_VALUE); 

     visted[x] = true; 

     // 初始化dist数组
     for (int i = 1; i < dist.length; i++) {
            if (!visted[i] && map[x][i] != 0) {
                dist[i] = map[x][i];
          }
      } 

     while (true) { 

          int temp = 0;
          int min = Integer.MAX_VALUE;
   
          //找出花费最少时间的路径
          for (int i = 1; i < dist.length; i++) {
             if (dist[i] < min && !visted[i]) {
             min = dist[i];
              temp = i;
            }
         }
         // x = temp;
          if (temp == 0)
                break;
          visted[temp] = true;
      
         //更新目前x到其他田的最短路径
          for (int i = 1; i < dist.length; i++) { 

          if (!visted[i] && map[temp][i] != 0
                && dist[i] > dist[temp] + map[temp][i]) {
                dist[i] = dist[temp] + map[temp][i];
           }
        }
     }
   } 
}

  1. 思路二可以用一个长度为k的队列来实现,入队后判断下队尾元素的next指针是否为空,若为空,则出队指针即为所求。