http://acm.zju.edu.cn/onlinejudge/showProblem.do?problemCode=2750成語接龍問題，抽象出來就是簡單的最簡單的單源最短路徑問題，Dijkstra算法。
算法設(shè)計(jì)課上剛講過貪心算法，Dijkstra算法書上有代碼實(shí)現(xiàn)，比著書上的代碼copy了一遍，提交后居然奇跡般的出現(xiàn)了段錯(cuò)誤！這叫我情何以堪啊。FAQ上說段錯(cuò)誤有兩種情況：數(shù)組下標(biāo)越界和棧溢出。算法中沒有遞歸，不可能爆棧，認(rèn)真檢查每一個(gè)用到下標(biāo)的地方、每個(gè)for的起始點(diǎn)，看不出任何毛病。難道代碼比著書上抄錯(cuò)了，對照了一下，發(fā)現(xiàn)第二個(gè)循環(huán)開始時(shí)沒有初始化u，問題就出在這里，u是用來記錄下一個(gè)可加入集合s的節(jié)點(diǎn)的，它的更新來自于所有可利用的dist[]中最下的那個(gè)。
經(jīng)驗(yàn)總結(jié)：變量不要忘記初始化。
#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
小鼠標(biāo) 閱讀(315)
評論(0) 編輯 收藏 引用 所屬分類:
圖論