首页 > 代码库 > poj1122 FDNY to the Rescue!(dij+反向建图+输出路径)
poj1122 FDNY to the Rescue!(dij+反向建图+输出路径)
题目链接：poj1122 FDNY to the Rescue!
题意：给出矩阵，矩阵中每个元素tij表示从第i个交叉路口到第j个交叉路口所需时间，若tij为-1则表示两交叉路口之间没有直接路径，再给出火警位置所在的交叉路口 和 一个或多个消防站所处的交叉路口位置。输出要求按消防站到火警位置所需时间从小到大排列，输出信息包括消防站位置（初始位置），火警位置（目标位置），所需时间，最短路径上每个交叉路口。
题解：反向建图，从火警位置求一次最短路，求最短路时记录路径，按时间从小到大输出。
1 #include<cstdio> 2 #include<cstring> 3 #include<algorithm> 4 #define CLR(a,b) memset((a),(b),sizeof((a))) 5 using namespace std; 6 7 const int inf = 0x3f3f3f3f; 8 const int N = 21; 9 int n, fire;10 int g[N][N];//邻接矩阵存图11 int s[N], d[N];12 int path[N];//表示v0到vi最短路径顶点vi的前一个顶点序号13 int shortest[N];//存储最短路径上的各个顶点序号14 struct node{15 int u, v, t;16 }a[N];17 int cmp(node a, node b){18 return a.t < b.t;19 }20 void dij(){21 int i, j, k;22 CLR(s, 0);23 for(i = 1; i <= n; ++i){24 d[i] = g[fire][i];25 if(i != fire)26 path[i] = fire;27 else28 path[i] = -1;29 }30 s[fire] = 1;31 d[fire] = 0;32 for(i = 0; i < n-1; ++i){33 int mi = inf, u = 0;34 for(j = 1; j <= n ; ++j){35 if(!s[j] && d[j] < mi){36 u = j; mi = d[j];37 }38 }39 s[u] = 1;40 for(k = 1; k <= n; ++k){41 if(!s[k] && d[u] + g[u][k] < d[k]){42 d[k] = d[u] + g[u][k];43 path[k] = u;44 }45 }46 }47 }48 int main(){49 int i, j, x, cnt;50 scanf("%d", &n);51 for(i = 1; i <= n; ++i){//边反向存储52 for(j = 1; j <= n; ++j){53 scanf("%d", &x);54 if(x == -1)55 g[j][i] = inf;56 else57 g[j][i] = x;58 }59 }60 scanf("%d", &fire);61 dij();62 cnt = 0;63 while(scanf("%d", &x) == 1){64 a[cnt].u = x;65 a[cnt].v = fire;66 a[cnt++].t = d[x];67 }68 sort(a, a+cnt, cmp);69 printf("Org\tDest\tTime\tPath\n");70 for(i = 0; i < cnt; ++i){71 printf("%d\t%d\t%d", a[i].u, a[i].v, a[i].t);72 CLR(shortest, 0);73 int k = 0;//表示shortest数组中最后一个元素的下标74 shortest[k] = a[i].u;75 while(path[shortest[k]] != -1){76 k++;77 shortest[k] = path[shortest[k-1]];78 }79 for(j = 0; j <= k; ++j) //倒向追踪，但是反向建图，因此正向输出80 printf("\t%d", shortest[j]);81 puts("");82 }83 return 0;84 }
poj1122 FDNY to the Rescue!(dij+反向建图+输出路径)
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。