HDU 1385 Minimum Transport Cost 最短路径题解

本题就是使用Floyd算法求所有路径的最短路径,并且需要保存路径,而且更进一步需要按照字典顺序输出结果。

还是有一定难度的。

Floyd有一种很巧妙的记录数据的方法,大多都是使用这个方法记录数据的。

不过其实本题数据不是很大,一般太大的数据也无法使用Floyd,因为效率是O(N^3)。

所以其实也可以使用一般的Floyd算法,然后增加个三维数组记录数据。下面就是这种做法,0ms过了.

#include #include using std::vector; vector checkDictOrder(vector a, vector b) { for (int i = 0; i b[i]) return b; } return a.size() > &gra, vector &tax, vector > > &paths) { int N = (int)gra.size(); for (int i = 0; i t = paths[i][k]; t.pop_back();//pop k out t.insert(t.end(), paths[k][j].begin(), paths[k][j].end()); if (gra[i][k]+gra[k][j]+tax[k]==gra[i][j]) paths[i][j] = checkDictOrder(t, paths[i][j]); else paths[i][j] = t; gra[i][j] = gra[i][k] + gra[k][j] + tax[k]; } } } } } int main() { int N, g, h; while (scanf("%d", &N) && N) { vector > gra(N, vector(N)); for (int i = 0; i tax(N); for (int i = 0; i > > paths(N, vector >(N)); FloydWarshall(gra, tax, paths); while (scanf("%d %d", &g, &h) && g != -1 && h != -1) { printf("From %d to %d :\nPath: ", g, h); g--, h--; if(g != h) { for (int u = 0; u+1 ", paths[g][h][u]+1); } } printf("%d\nTotal cost : %d\n\n", h+1, gra[g][h]); } } return 0; }



点击复制链接 与好友分享!回本站首页


您对本文章有什么意见或着疑问吗?请到论坛讨论您的关注和建议是我们前行的参考和动力
上一篇:HDU 3694 Fermat Point in Quadrangle (费马定理求四边形的费马点)
下一篇:HDU - 3555 Bomb (数位DP)
相关文章

华为面试题解析 - 01

华为面试题解析 - 02

华为面试题解析 - 03

华为面试题解析 - 04

华为面试题解析 - 05

华为面试题解析 - 06

bzoj2190仪仗队题解

SRM 589题解

博弈之nyoj 970 Yougth's Game

bzoj 1026 [SCOI2009]windy数 题解

图文推荐

HDU 1385 Minimum Transport Cost 最短路径题解
ZOJ 3640 Help Me
HDU 1385 Minimum Transport Cost 最短路径题解
CF 518C(Anya and
HDU 1385 Minimum Transport Cost 最短路径题解
hdu 1016 Prime R
UVA - 11987 - A
分类:默认分类 时间:2015-02-26 人气:1
本文关键词:
分享到:

相关文章

Copyright (C) quwantang.com, All Rights Reserved.

趣玩堂 版权所有 京ICP备15002868号

processed in 0.115 (s). 10 q(s)