P1629 邮递员送信 多源最短路_floyd

分析

1. 邮递员每送一个快递都要回去，一次送一个快递，可以判断出这是求多源的最短路，可以采用floyd算法
2. 而且此题为有向图，所以不能直接算个去的时候的时间，然后乘2，因为来回的路可能不一样
3. 需要注意此题在输入的时候，会有重复的路径，所以我们在处理输入的时候，要注意进行预处理，选取两点最短的路径
4. 此外我用getPath方法保存了某两点之间最短路径的情况
   
5. 保存路径我用的path数组，pass[i][j] 表示：更新从 i 到 j 的最短路径时，经过的一个中转点。然后用LinkedHashSet去保存所经过的点，可以去重，也可以使添加的顺序不会被改变；比如用ArrayList去保存路径，会出现重复；
   

java TLE 50分

import java.util.LinkedHashSet;
import java.util.Scanner;public class Main {static int n, m;static int inf = 10010;static int[][] d = new int[1010][1010];static int[][] path = new int[1010][1010];static LinkedHashSet<Integer> set = new LinkedHashSet<>();static void floyd() {for (int k = 0; k < n; k++) {for (int i = 0; i < n; i++) {for (int j = 0; j < n; j++) {if (d[i][j] > d[i][k] + d[k][j]) {d[i][j] = d[i][k] + d[k][j];path[i][j] = k;}}}}}static void getPath(int start, int end) {if (start == end)return;if (path[start][end] == 0) {set.add(start);set.add(end);} else {getPath(start, path[start][end]);getPath(path[start][end], end);}}public static void main(String[] args) {Scanner scan = new Scanner(System.in);n = scan.nextInt();m = scan.nextInt();for (int i = 0; i < n; i++) {for (int j = 0; j < n; j++) {if (i == j)d[i][j] = 0;elsed[i][j] = inf;}}for (int i = 0; i < m; i++) {int x = scan.nextInt();int y = scan.nextInt();int t = scan.nextInt();d[x - 1][y - 1] = Math.min(t, d[x - 1][y - 1]);//重复路径会重复输入}floyd();int ans = 0;for (int i = 1; i < n; i++) {ans += (d[0][i] + d[i][0]);}System.out.println(ans);
//        getPath(13, 29);
//        System.out.print("路径情况：");
//        for (Object o : set) {
//            System.out.print(o + "->");
//        }}
}

c++ AC
用了一个way数组来保存路径

#include 
using namespace std;
int n, m;
int d[1010][1010];
int path[1010][1010];
int way[10000];
int cnt = 0;
int inf = 10010;
void floyd() {for (int k = 1; k <= n; k++) //中转点for (int i = 1; i <= n; i++)for (int j = 1; j <= n; j++) {if (d[i][j] > d[i][k] + d[k][j]) {d[i][j] = d[i][k] + d[k][j];path[i][j] = k; //记录i到j需经过中转点k}}
}
void init() {for (int i = 1; i <= n; i++) {for (int j = 1; j <= n; j++) {if (i == j)d[i][j] = 0;elsed[i][j] = inf;}}for (int i = 1; i <= m; i++) {int x, y, val;cin >> x >> y >> val;d[x][y] = min(d[x][y], val); //通过样例发现会输入重复的路径，选最小的那条}
}
void get_path(int i, int j) {if (i == j)return;if (path[i][j] == 0) {way[++cnt] = i;} else {get_path(i, path[i][j]);get_path(path[i][j], j);}}
int main() {cin >> n >> m;init();floyd();int ans = 0;for (int i = 2; i <= n; i++) {ans += (d[1][i] + d[i][1]); //从出发点到i，再从i回到出发点}cout << ans << endl;
//	get_path(1, 4);
//	for (int i = 1; i <= cnt; i++) {
//		cout << way[i] << "->";
//	}return 0;
}

本文来自互联网用户投稿，文章观点仅代表作者本人，不代表本站立场，不承担相关法律责任。如若转载，请注明出处。 如若内容造成侵权/违法违规/事实不符，请点击【内容举报】进行投诉反馈！