poj1122&&zoj1053 FDNY to the Rescue! ——最短路入门题_Dijkstra算法
May 6, 2013
POJ
Graph
题目链接：http://poj.org/problem?id=1122 http://acm.zju.edu.cn/onlinejudge/showProblem.do?problemId=53 题目大意： 给定一个有向图，一个终点S，求多个点到这个点S的最短距离和对应的路径，把最短路排序后输出。 题目思路： 点的范围是20.可以一个一个用Dijkstra。。唯一的新意就是有多个点还需要按照路径长度排序，同时还要输出对应的路径，考的就是代码能力。用结构体存就可以。注意是有向图，开始就以为是无向图，怎么算最短路都不对。。赶脚这题不难，没什么思维难度，但是做OJ上这题的人却比较少，可能有一个原因，题目比较长，然后读完题目之后觉得没什么意思就不做了。。很简单的一个东西搞这么长的题目，也许就是考的读题吧。。貌似如果不是看的书上的翻译，我也没耐心读题。。。唉，读题确实是关键的一关。 然后这道题目，Poj上是单case，比较好过，然后数据也貌似比较弱，因为是单case，所以有一个输入的细节就特别好处理。开始Poj一下就过了，还沾沾自喜，结果把单case换成多case的时候，在zoj上交就Segmentation Fault……原来我最初处理输入个数不确定的数字的时候用了 while(~scanf())这种方法，很显然，这货只适用于单case。然后就想，该怎么处理这种输入数字个数不确定的输入呢？看了网上的一个思路，http://blog.csdn.net/yzldw333/article/details/7858172 哈哈，原来这么简单，就是以前做过的么，按照字符串处理就行了，，，好吧，，原来自己就是怕麻烦，这种方法想都没想。。然后就改了，，还是Segmentation Fault……继续调试，查错。。忍不住看了一下别人的代码，http://www.cnblogs.com/372465774y/archive/2012/11/19/2777552.html 一个注释提示了我，“这题给的字符真的是：t ‘ ’”好吧……我还真没注意到，虽然读题的时候注意到了，但是写代码的时候就想当然地只考虑空格，，像以前那样……思维定式啊。。然后就过了。。 Segmentation Fault的原因是访问了非法内存，在新的OJ上如果用的是Linux的话，归在Runtime Error一类里面。多谢zsl！ Poj代码：
#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <cctype>
#include <stack>
#include <queue>
#include <map>
#include <set>
#include <vector>
#include <cmath>
#include <algorithm>
#define lson l, m, rt<<1
#define rson m+1, r, rt<<1|1
using namespace std;
typedef long long int LL;
const int MAXN = 0x7fffffff;
const int MINN = -0x7fffffff;
const double eps = 1e-9;
const int dir[8][2] = {{0,1},{1,0},{0,-1},{-1,0},{-1,1},
{1,1},{1,-1},{-1,-1}};
const int MAX = 20;
int edge[MAX][MAX], n, dist[MAX], path[MAX], end;
bool S[MAX];
typedef struct Fire {
int street[MAX], len, start, E;
bool operator < (const Fire &other) const {
return len < other.len;
}
}Fire;
Fire fire[MAX];
void Dijkstra(int u0, Fire &su) {
int i, j, k, u, Min;
for (i = 1; i <= n; ++i) {
dist[i] = edge[u0][i]; S[i] = false;
if (i != u0 && edge[u0][i] != MAXN) path[i] = u0;
else path[i] = -1;
}
S[u0] = true; path[u0] = -1;
for (i = 1; i < n; ++i) {
Min = MAXN; u = u0;
for (j = 1; j <= n; ++j) {
if (S[j] == false && dist[j] < Min) {
Min = dist[j]; u = j;
}
}
S[u] = true;
for (j = 1; j <= n;++j) {
if (S[j] == false && edge[u][j] != MAXN) {
int tmp = edge[u][j] + dist[u];
if (tmp < dist[j]) {
dist[j] = tmp; path[j] = u;
}
}
}
if (u == end) break;
}
k = 0; su.street[k] = end; int ho = path[end];
while (ho != -1) {
su.street[++k] = ho; ho = path[ho];
}
su.E = k;
su.len = dist[end];
}
int main(void){
#ifndef ONLINE_JUDGE
freopen("poj1122.in", "r", stdin);
#endif
int i, j;
while (~scanf("%d", &n)) {
for (i = 1; i <= n; ++i) {
for (j = 1; j <= n; ++j) {
scanf("%d", &edge[i][j]);
if (edge[i][j] == -1) edge[i][j] = MAXN;
}
}
scanf("%d", &end);
printf("Org\tDest\tTime\tPath\n");
int cnt= 0, start;
while (~scanf("%d", &start)) {
fire[cnt].start = start;
Dijkstra(start, fire[cnt]);
cnt++;
}
sort(fire, fire+cnt);
for (i = 0; i < cnt; ++i) {
printf("%d\t%d\t%d\t", fire[i].start, end, fire[i].len);
for (j = fire[i].E; j > 0; --j) {
printf("%d\t", fire[i].street[j]);
}
printf("%d\n", fire[i].street[0]);
}
}
return 0;
}
Zoj代码： 注意第86行到96行
#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <cctype>
#include <stack>
#include <queue>
#include <map>
#include <set>
#include <vector>
#include <cmath>
#include <algorithm>
#define lson l, m, rt<<1
#define rson m+1, r, rt<<1|1
using namespace std;
typedef long long int LL;
const int MAXN = 0x7fffffff;
const int MINN = -0x7fffffff;
const double eps = 1e-9;
const int dir[8][2] = {{0,1},{1,0},{0,-1},{-1,0},{-1,1},
{1,1},{1,-1},{-1,-1}};
const int MAX = 30;
int edge[MAX][MAX], n, dist[MAX], path[MAX], end;
bool S[MAX];
typedef struct Fire {
int street[MAX], len, start, E;
bool operator < (const Fire &other) const {
return len < other.len;
}
}Fire;
Fire fire[MAX];
void Dijkstra(int u0, Fire &su) {
int i, j, k, u, Min;
for (i = 1; i <= n; ++i) {
dist[i] = edge[u0][i]; S[i] = false;
if (i != u0 && edge[u0][i] != MAXN) path[i] = u0;
else path[i] = -1;
}
S[u0] = true; path[u0] = -1;
for (i = 1; i < n; ++i) {
Min = MAXN; u = u0;
for (j = 1; j <= n; ++j) {
if (S[j] == false && dist[j] < Min) {
Min = dist[j]; u = j;
}
}
S[u] = true;
for (j = 1; j <= n;++j) {
if (S[j] == false && edge[u][j] != MAXN) {
int tmp = edge[u][j] + dist[u];
if (tmp < dist[j]) {
dist[j] = tmp; path[j] = u;
}
}
}
if (u == end) break;
}
k = 0; su.street[k] = end; int ho = path[end];
while (ho != -1) {
su.street[++k] = ho; ho = path[ho];
}
su.E = k;
su.len = dist[end];
}
int main(void){
#ifndef ONLINE_JUDGE
freopen("poj1122.in", "r", stdin);
#endif
int i, j, T;
scanf("%d", &T);
for (int I = 0; I < T; ++I)
{
scanf("%d", &n);
for (i = 1; i <= n; ++i) {
for (j = 1; j <= n; ++j) {
scanf("%d", &edge[i][j]);
if (edge[i][j] == -1) edge[i][j] = MAXN;
}
}
scanf("%d", &end);
printf("Org\tDest\tTime\tPath\n");
int cnt= 0, start;
getchar(); char ch[100]; gets(ch);
int len = strlen(ch);
for (i = 0; i < len; ++i) {
while (!isdigit(ch[i])) i++; // 果然不仅仅有空格！！
start = 0;
while (isdigit(ch[i]) && i < len) {
start = start * 10 + (ch[i]-'0');
i++;
}
fire[cnt].start = start;
Dijkstra(start, fire[cnt]);
cnt++;
}
sort(fire, fire+cnt);
for (i = 0; i < cnt; ++i) {
printf("%d\t%d\t%d\t", fire[i].start, end, fire[i].len);
for (j = fire[i].E; j > 0; --j) {
printf("%d\t", fire[i].street[j]);
}
printf("%d\n", fire[i].street[0]);
}
if (I != T-1) printf("\n");
}
return 0;
}
赶脚还是要认真读题啊，像今天这种细节。。就是一个致命的错误