友好城市,美团笔试题

1. 邻接矩阵存储图，n<= 100, 使用多源最短路算法Floyd算法（\(O(n^3)\)），求出重要城市之间最短路径。


2. 遍历所有可能的配对，找出最小路径代价。具体的，求出所有重要城市的全排列，让相邻两城市配对，累加路径代价，再更新最小代价。

import java.util.*;
public class Main {
static int res = Integer.MAX_VALUE;
static void floyd(int[][] dis, int n) {
for(int k=0; k for(int i=0; i for(int j=0; j // 用中间点k更新点i和点j之间的距离
if(dis[i][k] != -1 && dis[k][j] != -1 && (dis[i][j] == -1 || dis[i][j] > dis[i][k] + dis[k][j]))
dis[i][j] = dis[i][k] + dis[k][j];
}
}
}
}
static void dfs(int[][] dis, int[] c, int idx, int cost, int k) {
if(idx == 2*k && res > cost) { // 找出一个代价较小的排列，更新
res = cost; return;
}
for(int i=idx+1; i <2*k; i++) {
int t = c[idx+1]; c[idx+1] = c[i]; c[i] = t;
if(dis[c[idx]][c[idx+1]] != -1)
dfs(dis, c, idx+2, cost+dis[c[idx]][c[idx+1]], k);
t = c[idx+1]; c[idx+1] = c[i]; c[i] = t;
}
}
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
int n = sc.nextInt();
int[][] a = new int[n][n];
int[][] dis = new int[n][n];
for(int i=0; i for(int j=0; j a[i][j] = sc.nextInt();
dis[i][j] = a[i][j];
}
}
floyd(dis, n);
int k = sc.nextInt();
int[] city = new int[2*k];
for(int i=0; i <2*k; i++) city[i] = sc.nextInt()-1;
dfs(dis, city, 0, 0, k);
System.out.println(res);
}
}


友好城市, 美团笔试题