蓝桥杯算法提高VIP-文化之旅 （Java代码）

解题思路:

import java.util.*;   //Dijksdra
  
public class Main  {
	static int[][] dis;
	static int[] minDis;
	static int N;
	public static void Dijksdra(int src) {
		int[] vis = new int[N+1];
		for (int i = 1; i <= N; i++)
			minDis[i] = Integer.MAX_VALUE;
		minDis[src] = 0;
		for (int i = 1; i <= N; i++) {
			int u = -1;
			for (int j = 1; j <= N; j++)
				if (vis[j] == 0 && (u == -1 || minDis[u] > minDis[j])) u = j;
			vis[u] = 1;
			for (int j = 1; j <= N; j++) {
				if (vis[j] == 0 && dis[u][j] != 0 && minDis[u] != Integer.MAX_VALUE)
					minDis[j] = Math.min(minDis[u] + dis[u][j], minDis[j]);
			}
		}
	}
	
    public static void main(String args[]){  
    	Scanner input = new Scanner(System.in);
        N = input.nextInt();    //国家数
        int K = input.nextInt();    //文化数
        int M = input.nextInt();	//道路数
        int S = input.nextInt();	//起点
        int T = input.nextInt();	//终点
        int[] culture = new int[N+1];
        for (int i = 1; i <= N; i++)
        	culture[i] = input.nextInt();
        int[][] isreject = new int[K+1][K+1]; 
        for (int i = 1; i <= K; i++)
        	for (int j = 1; j <= K; j++)
        		isreject[i][j] = input.nextInt();   //文化i是否排斥j
        dis = new int[N+1][N+1];
        minDis = new int[N+1];
        for (int i = 1; i <= M; i++) {
        	int l = input.nextInt();
        	int r = input.nextInt();
        	int d = input.nextInt();
        	//判断两个国家之间文化是否排斥
        	if (isreject[culture[r]][culture[l]] == 0) {
        		if (dis[l][r] != 0)
        			dis[l][r] = Math.min(dis[l][r], d);
        		else
        			dis[l][r] = d;
        	}
        	if (isreject[culture[l]][culture[r]] == 0) {
        		if (dis[r][l] != 0)
        			dis[r][l] = Math.min(dis[r][l], d);
        		else
        			dis[r][l] = d;
        	}
        }
        Dijksdra(S);
        if (minDis[T] != Integer.MAX_VALUE)
        	System.out.println(minDis[T]);
        else
        	System.out.println(-1);
    }  
}

注意事项:





参考代码: