poj1122&zoj1053 FDNY to the Rescue!(dijkstra+输出路径)

发布时间:2016-12-11 0:55:15 编辑:www.fx114.net 分享查询网我要评论
本篇文章主要介绍了"poj1122&zoj1053 FDNY to the Rescue!(dijkstra+输出路径)",主要涉及到poj1122&zoj1053 FDNY to the Rescue!(dijkstra+输出路径)方面的内容,对于poj1122&zoj1053 FDNY to the Rescue!(dijkstra+输出路径)感兴趣的同学可以参考一下。

题目请戳这里(poj)或这里(zoj) 题目大意:n个点表示n个路口,任意2个路口可能有一条路,现在给定一个着火点和若干消防局,求所有消防局到着火点最短距离并输出路径,按找距离升序输出,按样例输出。 题目分析:裸的最短路,路径的话记录前驱就ok。由于有多个起点,一个终点,所以将终点当起点,原图是有向图,所以将原图建反图,在反图上dijkstra。 不过这题还是搞的很dt,poj是单case,zoj是多case,而且消防局数量不告诉,所以要自己判断有多少个,sscanf可以解决,但是由于这题的输入猥琐的使用了\t,水平制表符。。。所以sscanf就悲剧了。。。这点wa出翔了。。。\t看着像空格,但其实不是空格,占一个字节。 详情请见代码: #include <iostream> #include<cstdio> #include<cstring> #include<algorithm> using namespace std; const int N = 22; const int INF = 0x3f3f3f3f; int map[N][N]; int dis[N],path[N]; bool vis[N]; struct node { int org,tim; int pa[N],num; bool operator< (const struct node a)const { return tim < a.tim; } }ans[N]; int ansnum; int n,st,stnum; int station[N]; char str[1000]; void dijkstra() { int i,j,k,Min; for(i = 1;i <= n;i ++) { vis[i] = false; //dis[i] = INF; //path[i] = 0; dis[i] = map[st][i]; if(dis[i] != INF && i != st) path[i] = st; else path[i] = 0; } vis[st] = true; dis[i] = 0; for(i = 1;i < n;i ++) { Min = INF; k = st; for(j = 1;j <= n;j ++) { if(vis[j] == false && dis[j] < Min) { k = j; Min = dis[j]; } } vis[k] = true; for(j = 1;j <= n;j ++) { if(vis[j] == false && map[k][j] != INF && dis[j] > dis[k] + map[k][j]) { dis[j] = dis[k] + map[k][j]; path[j] = k; } } } } int main() { int i,j,tmp,t; scanf("%d",&t);//ZOJ while(t --) { scanf("%d",&n);// != EOF for(i = 1;i <= n;i ++) { for(j = 1;j <= n;j ++) { scanf("%d",&tmp); if(tmp == -1) tmp = INF; map[j][i] = tmp; } } while(getchar()!='\n'); //gets(str); //scanf("%d",&st); //while(scanf("%d",&station[stnum]) != EOF)poj // stnum ++; gets(str); stnum = 0; int p = 0; sscanf(str + p,"%d",&st); while(str[p] && str[p] == '\t')//坑爹。。。 p ++; while(str[p] && str[p] != '\t') p ++; while(sscanf(str + p,"%d",&station[stnum]) == 1) { stnum ++; while(str[p] && str[p] == '\t') p ++; while(str[p] && str[p] != '\t') p ++; } dijkstra(); for(i = 0;i < stnum;i ++) { ans[i].num = 0; ans[i].org = station[i]; ans[i].tim = dis[station[i]]; ans[i].pa[ans[i].num] = ans[i].org; while(path[ans[i].pa[ans[i].num]] != 0) { ans[i].num ++; ans[i].pa[ans[i].num] = path[ans[i].pa[ans[i].num - 1]]; } ans[i].num ++; } sort(ans,ans + stnum); printf("Org\tDest\tTime\tPath\n"); for(i = 0;i < stnum;i ++) { printf("%d\t%d\t%d\t",ans[i].org,st,ans[i].tim); for(j = 0;j < ans[i].num - 1;j ++) printf("%d\t",ans[i].pa[j]); printf("%d\n",st); } if(t) puts(""); } return 0; } //128K 0MS

上一篇:编写好代码的10条戒律
下一篇:SVN的trunk branch tag

相关文章

相关评论