首页 > 代码库 > POJ 1122 FDNY to the Rescue! Floyd 打印路径就行了
POJ 1122 FDNY to the Rescue! Floyd 打印路径就行了
题目大意：
纽约消防部门的支援速度是值得纽约人骄傲的一件事。但是他们想要最快的支援速度，帮助他们提升支援速度他们要调度离着火点最近的一个消防站。他们要你写一个程序来维护纽约消防站的光荣传统。软件需要有的功能是，能获取着火点的地址 和 消防站的位置， 街道交叉路口， 从一个交叉路口到达另一个交叉路口的时间。 他将要计算从消防站到达着火点需要多少时间。
给你一个具体的着火点的地址，这个软件应该找出所有消防站到达着火点的距离， 并且从小到大进行排序。以便消防员来调度人员到达救火地点。
#include <iostream>#include <cstdlib>#include <cstdio>#include <algorithm>#include <vector>#include <queue>#include <cmath>#include <cstring>using namespace std;#define INF 0xfffffff#define maxn 40struct Point{ int e, w;} dist[maxn];bool cmp(Point A,Point B){ return A.w < B.w;}int Path[maxn][maxn], G[maxn][maxn], n;void Floyd(){ for(int k=1; k<=n; k++) { for(int i=1; i<=n; i++) { for(int j=1; j<=n; j++) { if(G[i][j] > G[i][k] + G[k][j] ) { G[i][j] = G[i][k] + G[k][j]; Path[i][j] = Path[i][k]; } } } }}void PutPath(int Star,int End){ while(Star != End) { printf("\t%d", Star); Star = Path[Star][End]; } printf("\t%d\n", Star);}int main(){ int a; cin >> n; for(int i=1; i<=n; i++) { for(int j=1; j<=n; j++) { Path[i][j] = j; cin >> G[i][j]; if(G[i][j] == -1) G[i][j] = INF; } } int End, k = 0; Floyd(); cin >> End; while(scanf("%d",&a) != EOF) { dist[k].w = G[a][End]; dist[k++].e = a; } sort(dist, dist + k, cmp); cout << "Org\tDest\tTime\tPath" << endl; for(int i=0; i<k; i++) { printf("%d\t%d\t%d", dist[i].e, End, G[dist[i].e][End]); PutPath(dist[i].e, End); } return 0;}
POJ 1122 FDNY to the Rescue! Floyd 打印路径就行了
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。