首页 > 代码库 > POJ--1122--FDNY to the Rescue!【最短路】
POJ--1122--FDNY to the Rescue!【最短路】
题意:给你一个邻接矩阵信息,某点发生火灾,告诉你一些位置有消防队,问各个消防队到火灾地点的最短时间,并输出最短路的路径,输出按最短时间由小到大排序。
就是一个最短路问题,输出路径,直接dijkstra了,1A还是挺爽的
#include<cstring> #include<string> #include<fstream> #include<iostream> #include<iomanip> #include<cstdio> #include<cctype> #include<algorithm> #include<queue> #include<map> #include<set> #include<vector> #include<stack> #include<ctime> #include<cstdlib> #include<functional> #include<cmath> using namespace std; #define PI acos(-1.0) #define MAXN 100010 #define eps 1e-7 #define INF 0x7FFFFFFF #define seed 131 #define long long ll; #define unsigned long long ull; #define lson l,m,rt<<1 #define rson r,m+1,rt<<1|1 struct node{ int id, s, time, pathl; int path[25]; }ans[25]; int edge[25][25]; int vis[25]; int dist[25]; int path[25]; int n; bool cmp(node x,node y){ return x.time<y.time; } void dijkstra(int s,int e){ int i, j; for(i=1;i<=n;i++){ dist[i] = edge[s][i]; } memset(vis,0,sizeof(vis)); memset(path,0,sizeof(path)); vis[s] = 1; for(i=0;i<n-1;i++){ int temp = INF, k = -1; for(j=1;j<=n;j++){ if(!vis[j]&&dist[j]<temp){ k = j; temp = dist[j]; } } if(k==-1) break; vis[k] = 1; for(j=1;j<=n;j++){ if(!vis[j]&&edge[k][j]!=INF&&dist[j]>dist[k]+edge[k][j]){ dist[j] = dist[k] + edge[k][j]; path[j] = k; } } } } int main(){ int i, j, s, e, x; scanf("%d",&n); for(i=1;i<=n;i++){ for(j=1;j<=n;j++){ scanf("%d",&x); if(x==-1) edge[i][j] = INF; else edge[i][j] = x; } } scanf("%d",&e); int k = 0; printf("Org\tDest\tTime\tPath\n"); while(scanf("%d",&s)!=EOF){ dijkstra(s,e); ans[k].id = k + 1; ans[k].s = s; ans[k].time = dist[e]; ans[k].pathl = 1; int ll = 1; ans[k].path[0] = e; int ee = e; while(path[ee]!=0){ ans[k].path[ll++] = path[ee]; ee = path[ee]; ans[k].pathl++; } ans[k].path[ll++] = s; ans[k].pathl++; if(ans[k].pathl==2&&ans[k].path[0]==ans[k].path[1]) ans[k].pathl = 1; k++; } sort(ans,ans+k,cmp); for(i=0;i<k;i++){ printf("%d\t%d\t%d\t",ans[i].s,e,ans[i].time); for(j=ans[i].pathl-1;j>0;j--){ printf("%d\t",ans[i].path[j]); } printf("%d\n",ans[i].path[j]); } printf("\n"); return 0; } /* 6 0 3 4 -1 -1 -1 -1 0 4 5 -1 -1 2 3 0 -1 -1 2 8 9 5 0 1 -1 7 2 1 -1 0 -1 5 -1 4 5 4 0 5 5 */
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。