http://acm.zju.edu.cn/onlinejudge/showProblem.do?problemCode=2750成语接龙问题，抽象出来就是简单的最简单的单源最短路径问题，Dijkstra算法。
算法设计课上刚讲过贪心算法，Dijkstra算法书上有代码实现，比着书上的代码copy了一遍，提交后居然奇迹般的出现了段错误！这叫我情何以堪啊。FAQ上说段错误有两种情况：数组下标越界和栈溢出。算法中没有递归，不可能爆栈，认真检查每一个用到下标的地方、每个for的起始点，看不出任何毛病。难道代码比着书上抄错了，对照了一下，发现第二个循环开始时没有初始化u，问题就出在这里，u是用来记录下一个可加入集合s的节点的，它的更新来自于所有可利用的dist[]中最下的那个。
经验总结：变量不要忘记初始化。
#include<stdio.h>
#include<string.h>
#include<stdlib.h>
#define LENID 1050
#define RMAX 10000
#define LENS 8
typedef struct
{
char *a;
char *b;
int t;
}Idiom;
int N;
int dist[LENID];
int c[LENID][LENID];
int Dijkstra()
{
int i, j;
int s[LENID];
for(i = 0; i < N; i++)// init
{
dist[i] = c[0][i];
s[i] = 0;
}
dist[0] = 0;
s[0] = 1;
int u = 0;// remeber to init u!!
for(i = 0; i < N - 1; i++)
{
int temp = RMAX;
for(j = 0; j < N; j++)
{
if(s[j] == 0 && dist[j] < temp)
{
u = j;
temp = dist[j];
}
}
s[u] = 1;
if(u == N - 1)
{
return dist[u];
}
for(j = 0; j < N; j++)
{
if(s[j] == 0 && c[u][j] < RMAX)
{
int newdist = dist[u] + c[u][j];
if(newdist < dist[j])
dist[j] = newdist;
}
}
}
return dist[N - 1];
}
int main()
{
int T;
int i, j;
Idiom id[LENID];
char str[100], sa[8], sb[LENS];
scanf("%d", &N);
while(N != 0)
{
for(i = 0; i < N; i++)
{
scanf("%d%s", &T, str);
int len = strlen(str);
for(j = 0; j < 4; j++)
{
sa[j] = str[j];
sb[j] = str[len - 4 + j];
}
sa[j] = sb[j] = '\0';
id[i].a = (char *)malloc(sizeof(char) * LENS);
id[i].b = (char *)malloc(sizeof(char) * LENS);
strcpy(id[i].a, sa);
strcpy(id[i].b, sb);
id[i].t = T;
}
for(i = 0; i < N; i++)// init c[][]
for(j = 0; j < N; j++)
c[i][j] = RMAX;
for(i = 0; i < N; i++)
for(j = i + 1; j < N; j++)
{
if(strcmp(id[i].b, id[j].a) == 0)
c[i][j] = id[i].t;
else if(strcmp(id[j].b, id[i].a) == 0)
c[j][i] = id[j].t;
}
int r = Dijkstra();
if(r == RMAX)
printf("-1\n");
else
printf("%d\n", r);
scanf("%d", &N);
}
}
posted on 2012-04-25 18:08
小鼠标 阅读(294)
评论(0) 编辑 收藏 引用 所属分类:
图论