Chinaunix

标题: 地接斯特拉，距离 268435456 是怎么得到的？ [打印本页]

作者: 慢跑20 时间: 2014-05-30 09:48
标题: 地接斯特拉，距离 268435456 是怎么得到的？
#include <stdio.h>
#include <string.h>
#include <math.h>
#define bool int
#define true 1
#define false 0
#define maxedge 20
#define maxn 9  //结点数
#define inf 1<<28
bool vist[maxn];
struct Edge
{
int s; //边的起点
int t; //边的终点
int next;//当前下一条边的编号
int w;  //边的权值
}edge[maxedge];
int headlist[maxedge]; //索引  head[i]存放已i为起点的“第一条”边
int distance[maxn];
int n,m,x;
void dij()
{
int i,j,k;
//memset(vist,false,sizeof(vist));
j=sizeof(vist);
for(i=0;i<j;i++)
    vist[i]=0;
for(i=1;i<=n;++i)
   distance[i]=inf;
   distance[x]=0;
for(i=1;i<=n;i++)
{ k=-1;
      for(j=1;j<=n;j++)
      if(!vist[j]&&(k==-1||distance[k]>distance[j]))
         k=j;
      vist[k]=true;
      for(j=headlist[k];j!=-1;j=edge[j].next)
      if(!vist[edge[j].t]&&(distance[k]+edge[j].w<distance[edge[j].t]))
         distance[edge[j].t]=distance[k]+edge[j].w;
}
printf("distance are:");

   for(i=1;i<=n;i++)
  printf("从点%d到点%d的距离是：%d  \n",x,i-1,distance[i]);
// printf("%d  ",distance[i]);
}
int main()
{
int i,a,b,c;
printf("请输入请输入定点数、边数,起始点\n");
while(~scanf("%d%d%d",&n,&m,&x))
{
printf("顶点数、边数,起始点分别为：%d，%d，%d\n",n,m,x);
      for(i=1;i<=n;++i)
      headlist[i]=-1;
      for(i=1;i<=m;++i)
      {
printf("请输入第%d条边的起点、终点、权值\n",i);
         scanf("%d%d%d",&a,&b,&c);
         edge[i].s=a;
         edge[i].t=b;
         edge[i].w=c;
         edge[i].next=headlist[a];//索引：节点i 后一条边编号为headlist[a]；
         headlist[a]=i;

      }
      dij();
printf("\n算的没错吧，再来一次吧。\n\n请输入定点数、边数,起始点：\n");
}

return 0;
}

1.
//memset(vist,false,sizeof(vist));
和j=sizeof(vist);
for(i=0;i<j;i++)
    vist[i]=0;
作用是一样的吧？
2.得到的结果没问题，不过，如果无法达到，显示：268435456.268435456为什么是无穷大呢？这个怎么得到的？

作者: hellioncu 时间: 2014-05-30 09:58

268435456 = 0x10000000，就是你自己初始化的 #define inf 1<<28

作者: 慢跑20 时间: 2014-05-30 13:45
回复 2# hellioncu

原来如此啊。。。非常感谢！！

欢迎光临 Chinaunix (http://bbs.chinaunix.net/)