首页 > 代码库 > POJ1502: MPI Maelstrom
POJ1502: MPI Maelstrom
红果果的dijstra算法应用，这里采用邻接表存储图。
小插曲：while(scanf("%d",&n)）提交时内存超限，改成while(scanf("%d",&n)！=EOF）就AC了，不知道为什么
dijstra算法应用：已知定点为输入，输入图中所有其他点到该定点的最短距离。
具体做法：
a.初始时，S只包含源点，即S＝{v}，v的距离为0。U包含除v外的其他顶点，即:U={其余顶点}，若v与U中顶点u有边，则<u,v>正常有权值，若u不是v的出边邻接点，则<u,v>权值为∞。
b.从U中选取一个距离v最小的顶点k，把k，加入S中（该选定的距离就是v到k的最短路径长度）。
c.以k为新考虑的中间点，修改U中各顶点的距离；若从源点v到顶点u的距离（经过顶点k）比原来距离（不经过顶点k）短，则修改顶点u的距离值，修改后的距离值的顶点k的距离加上边上的权。
d.重复步骤b和c直到所有顶点都包含在S中。
1 #include<iostream> 2 #include<cstdio> 3 #include<algorithm> 4 #include<cstring> 5 #include<cmath> 6 using namespace std; 7 const int max_size=101; 8 const int MAXINT=9999999; 9 typedef struct arcNode{ 10 int node; 11 int len; 12 arcNode *next; 13 }arcNode; 14 typedef struct headNode{ 15 arcNode *firstArc; 16 }adjList[max_size]; 17 typedef struct cmap{ 18 adjList map; 19 int nodeNum, arcNum; 20 }cmap; 21 int n; 22 int st,ed; 23 int dis[max_size]; 24 bool vis[max_size]; 25 void initiate(cmap *c){ 26 for(int i=1;i<=c->nodeNum;i++){ 27 c->map[i].firstArc=NULL; 28 } 29 } 30 void addEdge(cmap *c,int from,int to,int len){ 31 if(from==to) return; 32 arcNode *arc=(arcNode *)malloc(sizeof(arcNode)); 33 arc->node=to; 34 arc->len=len; 35 arc->next=c->map[from].firstArc; 36 c->map[from].firstArc=arc; 37 38 arcNode *arcc=(arcNode *)malloc(sizeof(arcNode)); 39 arcc->node=from; 40 arcc->len=len; 41 arcc->next=c->map[to].firstArc; 42 c->map[to].firstArc=arcc; 43 44 } 45 /* 46 void print(cmap *c){ 47 for(int i=1;i<=c->nodeNum;i++){ 48 arcNode *p=c->map[i].firstArc; 49 while(p){ 50 printf("(%d)%d ",p->len,p->node); 51 p=p->next; 52 } 53 printf("\n"); 54 } 55 } 56 */ 57 void dijstra(cmap *c){ 58 int ans=-1; 59 arcNode *p=c->map[st].firstArc; 60 memset(dis,MAXINT,sizeof(dis)); 61 memset(vis,false,sizeof(vis)); 62 while(p){ 63 dis[p->node]=p->len; 64 p=p->next; 65 } 66 dis[st]=0; 67 vis[st]=true; 68 69 for(int i=1;i<=c->nodeNum-1;i++){ 70 int min_dist=9999999; 71 int u; 72 for(int j=1;j<=c->nodeNum;j++){ 73 if(!vis[j]&&dis[j]<min_dist){ 74 min_dist=dis[j]; 75 u=j; 76 } 77 } 78 vis[u]=true; 79 arcNode *p=c->map[u].firstArc; 80 while(p){ 81 int len=p->len; 82 int temp=p->node; 83 if(!vis[temp]&&min_dist+len<dis[temp]){ 84 dis[temp]=min_dist+len; 85 } 86 p=p->next; 87 } 88 89 } 90 for(int i=2;i<=c->nodeNum;i++){ 91 if(dis[i]>ans) ans=dis[i]; 92 } 93 printf("%d\n",ans); 94 } 95 int main(){ 96 while(scanf("%d",&n)!=EOF){ 97 cmap *c=(cmap *)malloc(sizeof(cmap)); 98 c->nodeNum=n; c->arcNum=n*n/2; 99 initiate(c);100 st=1;101 char tmp[20];102 for(int i=1;i<=n-1;i++){103 for(int j=1;j<=i;j++){104 scanf("%s",tmp);105 if(tmp[0]==‘x‘) addEdge(c,i+1,j,MAXINT);106 else addEdge(c,i+1,j,atoi(tmp));107 }108 }109 //print(c); 110 dijstra(c);111 }112 return 0;113 }
POJ1502: MPI Maelstrom
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。