初始化及变量设置
#define MANX 3500 #define INF 99999999 book[MANX],dis[MANX],e[MANX][MANX]//e表示邻接矩阵 for(i=1;i<=n;i++) for(j=1;j<=n;j++) if(i!=j)e[i][j]=INF;
设有n个顶点,用一个n*n的二维数组进行储存,下标表示连接到的两点,内容表示距离
for(i=1;i<=m;i++){ scanf("%d%d%d",&a,&b,&c); if(e[a][b]==INF||e[a][b]>c){ e[a][b]=c; e[b][a]=c; } }
用五个数组,分别是w,u,v,first,next(w保存权值,u,v分别表示该边连接的两点,用first与next的关系进行图之间的关系连接)
for(i=1;i<=n;i++) first[i]=-1; for(i=1;i<=m;i++){ cin>>u[i]>>v[i]>>w[i]; next[i]=first[u[i]]; first[u[i]]=i; }
说明:next数组储存有关边的编号,从而用数组进行查找,而first[i]储存的则是点i最后连接的边的编号,不过之前的也不用担心丢失,next帮你存好了。
遍历代码如下
for(i=1;i<=n;i++){ k=first[i]; while(k!=-1){ cout<<u[k]<<" "<<v[k]<<" "<<w[k]<<endl; k=next[k]; } }
原文:https://www.cnblogs.com/dancemu/p/10772081.html