坑爹的最短径.doc

《坑爹的最短径.doc》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、注意是无向图。那么输入的时候就要赋两次。关键之处在于定义MAX的那个最大值。这个是最坑人的地方。WA了无数次纠结了无数次。那个这个MAX到底要定义为多大的值呢？不在乎它的值的大小，而是输入的时候要做一下处理，当输入的值超过了MAX时，而你又直接给赋值的话，那你处理的时候不出现了比最大值还大的情况！！！当输入大于MAX是，我们就默认它是不通的。证据在此。。。。。。呵呵…附加上求最短路径的算法：再加上一个图方便理解可以copy的：voidshortpath_DIJ(intad[][M],intk,intpre[],intdist[],intn){i

2、nti,j,p,wm;for(i=0;i

3、p]=1;//p点加入S中for(i=0;i#include#defineM1050#defineMAX99999999intad[M][M][2],dist[M],cost[M],start,finish,n;voidshortpath()

4、{inti,j,p,wm,ww;for(i=1;i<=n;i++)//初始化dist,cost{dist[i]=ad[start][i][0];cost[i]=ad[start][i][1];}ad[start][start][0]=1;//标记for(j=1;j<=n-1;j++){ww=wm=MAX;//wm，ww存放T中最小的dist,cost值p=0;//p存储wm对应的编号for(i=1;i<=n;i++){if(!ad[i][i][0])if(dist[i]

5、(dist[i]==wm&&cost[i]

6、ad[p][i][0]==dist[i])if(cost[p]+ad[p][i][1]

7、}for(i=1;i<=cas;i++){scanf("%d%d%d%d",&a,&b,&sh,&co);if(sh