解题思路:
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); } }
注意事项:
参考代码:
0.0分
0 人评分
C语言程序设计教程(第三版)课后习题8.2 (Java代码)浏览:2269 |
C语言训练-求1+2!+3!+...+N!的和 (C语言代码)浏览:536 |
【亲和数】 (C语言代码)浏览:856 |
C语言训练-求函数值 (C语言代码)浏览:573 |
【简单计算】 (C语言代码)浏览:622 |
C语言程序设计教程(第三版)课后习题8.5 (C语言代码)浏览:935 |
Hello, world! (C语言代码)浏览:714 |
C语言程序设计教程(第三版)课后习题1.5 (C语言代码)浏览:399 |
Tom数 (C语言代码)浏览:552 |
1197求助浏览:629 |