首页 > 试题广场 >

I Wanna Go Home

[编程题]I Wanna Go Home

热度指数：9501 时间限制：C/C++ 1秒，其他语言2秒空间限制：C/C++ 64M，其他语言128M
算法知识视频讲解

The country is facing a terrible civil war----cities in the country are divided into two parts supporting different leaders. As a merchant, Mr. M does not pay attention to politics but he actually knows the severe situation, and your task is to help him reach home as soon as possible. "For the sake of safety,", said Mr.M, "your route should contain at most 1 road which connects two cities of different camp." Would you please tell Mr. M at least how long will it take to reach his sweet home?

输入描述:

    The input contains multiple test cases.
    The first line of each case is an integer N (2<=N<=600), representing the number of cities in the country.
    The second line contains one integer M (0<=M<=10000), which is the number of roads.
    The following M lines are the information of the roads. Each line contains three integers A, B and T, which means the road between city A and city B will cost time T. T is in the range of [1,500].
    Next part contains N integers, which are either 1 or 2. The i-th integer shows the supporting leader of city i. 
    To simplify the problem, we assume that Mr. M starts from city 1 and his target is city 2. City 1 always supports leader 1 while city 2 is at the same side of leader 2. 
    Note that all roads are bidirectional and there is at most 1 road between two cities.
Input is ended with a case of N=0.

输出描述:

    For each test case, output one integer representing the minimum time to reach home.
    If it is impossible to reach home according to Mr. M's demands, output -1 instead.

示例1

输入

输出

100
90
540

算法知识视频讲解

Java

/xinCupid☆

求个test case，跑代码的时候越栈了。例子给的三个都能过。

顺便帖下我的代码，想法是用dfs去做。

import java.util.*;
public class Main {
    static int M;
    static int N;
    static int[][] cost;
    static int[] sup;
    public static boolean isValid(int[] forCity) {
        return (forCity[1] == 1 && forCity[2] == 1 || Math.abs(forCity[1] - forCity[2]) >= 1);
    }
    public static void helper(int row, int sum, ArrayList<Integer> res, int[] forCity, int prev) {
        for (int col = 1; col < M+10; ++col) {
            if (prev == col) {
                continue;
            }
            if (cost[row][col] > 0) {
                forCity[sup[col]]++;
                if (isValid(forCity)) {
                    sum += cost[row][col];
                    if (col == 2) {
                        res.add(sum);
                    } else {
                        helper(col, sum, res, forCity, row);
                    }
                    sum -= cost[row][col];
                }
                forCity[sup[col]]--;
            }
        }
    }
    public static void main(String[] args) {
        Scanner reader = new Scanner(System.in);
        while (reader.hasNext()) {
            N = reader.nextInt();
            if (N == 0)
                return;
            M = reader.nextInt();
            cost = new int[M+10][M+10];
            for (int i = 1; i <= M; ++i) {
                int s = reader.nextInt();
                int e = reader.nextInt();
                int c = reader.nextInt();
                cost[s][e] = c;
                cost[e][s] = c;
            }
            sup = new int[M+10];
            for (int i = 1; i <= N; ++i) {
                sup[i] = reader.nextInt();
            }
            int sum = 0;
            ArrayList<Integer> res = new ArrayList<>();
            int[] forCity = new int[]{1, 1, 0};
            helper(1, sum, res, forCity, 0);
            if (res.size() > 0)
                System.out.println(Collections.min(res));
            else 
                System.out.println(-1);
        }
    }
}

发表于 2018-03-31 16:17:09 回复(0)

Java

一§切随＆缘！

说好的,两个城市之间只有至多一条路的呢?(你仿佛在逗我,假装有表情包)
import java.util.Scanner;

/*
 *	QQ:	825580813(一起来敲代码)
 *	思路:
 *		1,最短路径的修改版
 *		2,添加一个标记数组,判断走到当前城市是否已经穿越了两个阵营
 */
public class IWannaGoHome {

	static int n, m;
	static int[][] graph;
	static int[] camp;

	static final int max = 1000000;

	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		while ((n = sc.nextInt()) != 0) {
			m = sc.nextInt();
			graph = new int[n][n];
			for (int i = 0; i < n; ++i) {
				for (int j = 0; j < n; ++j) {
					graph[i][j] = i != j ? max : 0;
				}
			}
			for (int i = 0; i < m; ++i) {
				int start = sc.nextInt();
				int end = sc.nextInt();
				int time = sc.nextInt();
				if (time < graph[start - 1][end - 1]) {
					graph[start - 1][end - 1] = graph[end - 1][start - 1] = time;
				}
			}
			camp = new int[n];
			for (int i = 0; i < n; ++i) {
				camp[i] = sc.nextInt();
			}
			int res = getMinTime();
			System.out.println(res);
		}
		sc.close();
	}

	private static int getMinTime() {
		int[] minTime = new int[n]; 		// 最少花费时间
		boolean[] flag = new boolean[n]; 	// 是否穿过两个阵营
		boolean[] walked = new boolean[n];// 该城市是否走过
		for (int i = 1; i < n; ++i) {
			minTime[i] = max;
		}
		minTime[0] = 0;

		int start = 0;
		int curMin = max;
		for (int i = 0; i < n; ++i) {
			curMin = max;
			for (int j = 0; j < n; ++j) {
				if (!walked[j] && curMin > minTime[j]) {
					curMin = minTime[j];
					start = j;
				}
			}
			walked[start] = true;
			if (start == 1) {
				return curMin;
			}
			for (int j = 0; j < n; ++j) {
				if (!walked[j] && curMin + graph[start][j] < minTime[j]) {
					if (flag[start]) {		//如果走到start城市已经穿越了两个阵营
						if (camp[start] == camp[j]) {	//只能走与start相同的阵营
							minTime[j] = curMin + graph[start][j];
							flag[j] = true;				//并且j阵营也被纳入已穿越的阵营
						}
					} else {				//如果走到start城市还没穿越了两个阵营
						minTime[j] = curMin + graph[start][j];	//那么都可以走到j城市
						if (camp[start] != camp[j]) {		//如果start与j的阵营不同,
							flag[j] = true;		//那么j阵营就被纳入穿越的阵营
						}
					}
				}
			}
		}
		return minTime[1] == max ? -1 : minTime[1];
	}

}

发表于 2017-05-25 16:37:39 回复(1)