ACM 图论 用模板好吗？

模板可以偶尔用扒游用，但是关键是学其中的算法和思想，不能依赖摸板，所以说尽量不要用模板，实在不行的话先套用一虚雀下，下次尽量就不要套用了，acm牛人们都春誉销是不用模板或者很少用模板的

#include <cstdio>

#include <cstring>

//单源最短路径,用于路权相等的情况,dijkstra优化为bfs,邻接表形式,复杂度O(m)

//求出源s到所有点的最短路经,传入图的大小n和邻接表list,边权值len

//返回到各点最短距离min[]和路径pre[],pre[i]记录s到i路径上i的父结点,pre[s]=-1

//可更改路权类型,但必须非负且相等!

#define MAXN 200

#define inf 1000000000

typedef int elem_t

struct edge_t{

int from,to

edge_t* next

}

void dijkstra(int n,edge_t* list[],elem_t len,int s,elem_t* min,int* pre){

edge_t* t

int i,que[MAXN],f=0,r=0,p=1,l=1

for (i=0i<ni++)

min[i]=inf

min[que[0]=s]=0,pre[s]=-1

for (r<=fl++,r=f+1,f=p-1)

for (i=ri<=fi++)

for (t=list[que[i]]tt=t->next)

if (min[t->to]==inf)

min[que[p++]=t->to]=len*l,pre[t->to]=que[i]

}

//**********以上模板的demo

//以下声明节点池，这样比动态分配节点要快一些

const int MAXE=40000

edge_t edgePool[MAXE]

int size

// 以下声明邻接表

edge_t* list[MAXN+1]

elem_t len//每条边的权值

int s//bfs的源点

elem_t min[MAXN+1]//每一点耐高到源卜亩模点s的最短距离

int pre[MAXN+1]//bfs搜索树，每一点的前驱节点的编号

int n//顶点数，假定顶点编号从0到n-1

int m//边数

//在邻接表list中插入一条有向边from->to

void insert(edge_t* list[],int from,int to)

{

//初始化一个节点

edgePool[size].from=from

edgePool[size].to=to

//插入到边表头部

edgePool[size].next=list[from]

list[from]=&edgePool[size++]

}

void outputPath(int pre[],int i)

{

if(pre[i]==-1)

{

printf("%d",i)

return

}

outputPath(pre,pre[i])

printf("-->%d",i)

}

int main()

{

printf("Input the number of vertexs: ")

scanf("%d",&n)//读入定点数

printf("Input the number of edges: ")

scanf("%d",&m)//读入边数

//邻接表初始化

memset(list,0,sizeof(list))

size=0

//开始读入

printf("Input %d pairs of positive integers for all edges:\n",m)

printf("Notice that the vertexs is numbered from 0.\n")

for(int i=0i<mi++)

{

int x,y

scanf("%d %d",&x,&y)

insert(list,x,y)

insert(list,y,x)//无向图的话，正向反向插入两次

}

printf("Input the weight of each edge: "型缓)

scanf("%d",&len)//读入边权

printf("Input the source of the graph: ")

scanf("%d",&s)//读入源点

dijkstra(n,list,len,s,min,pre)

printf("*****Output the answer*****\n")

for(int i=0i<ni++)

{

if(min[i]==inf)//不连通

printf("There is no path to connect %d and %d.",s,i)

else

{

//输出s到i的最短距离

printf("The shortest distance from %d to %d is %d.\n",s,i,min[i])

//输出s到i的最短路径

printf("The shortest path from %d to %d is: ",s,i)

outputPath(pre,i)

}

printf("\n\n")

}

return 0

}

---