一道关于最短路径的题目ACM C语言

2025-03-07 08:11:53
推荐回答(2个)
回答1:

你这个程序写得让人生气。变量太多了,中间还没printf语句提示输入,注释一个也没有
代码书写可读性太差了。花好大力气把你变量干什么搞清楚啦,可是我都懒得去想你那程序中心代码为啥错啦。最短路径就是地杰斯特拉算法,我也不太熟,你自己好好揣摩吧。
#include
#define infinity 10000
#define len 100
int main()
{
int i,j,t,num,row,d,cost;
int v,f;
int map[len][len],s[len],dist[len],distm[len],mapm[len][len];
while(scanf("%d%d",&num,&row)!=EOF && num!=0 && row!=0)
{
for(i=0;i for(j=0;j {
map[i][j]=infinity;
mapm[i][j]=infinity;
}
printf("input the infor:\n");
for(t=1;t<=row;t++)
{
scanf("%d %d %d %d",&i,&j,&d,&cost);
if(map[i][j]>d)
{
map[j][i]=map[i][j]=d;
mapm[j][i]=mapm[i][j]=cost;
}
}
printf("input the two node:\n");
scanf("%d %d",&v,&f);
for(j=1;j<=num;j++) //initialize
{
s[j]=1;
dist[j]=map[v][j];
distm[j]=mapm[v][j];
}
dist[v]=0;
s[v]=0;
int u,min;
for(i=1;i<=num;i++)
{
min=infinity;
for(j=1;j<=num;j++)
if(s[j] && dist[j] {
min=dist[j];
u=j; //u to record the minimum
}
if(min==infinity) break;
s[u]=0;
for(j=1;j<=num;j++)
if(s[j])
{
if(dist[u]+map[u][j] {
dist[j]=dist[u]+map[u][j];
distm[j]=distm[u]+mapm[u][j];
}
else if(dist[u]+map[u][j]==dist[j]&&(distm[u]+mapm[u][j] distm[j]=distm[u]+mapm[u][j];

}
}
printf("%d %d\n",dist[f],distm[f]);
}
}

回答2:

拿你的代码做了实验,后面的全部注释掉,只留数组定义那一行就通不过
应该是大数组的堆栈溢出问题,你定义的数组1009*1009*4=4M,vc默认栈超过1M就完蛋啊
用动态的吧,还省内存空间
后面的代码问题也不少,比如路径长度和权重的赋值,明显出了问题,下标是要减一的。之后的没看,先解决这些再说吧