题目链接:http://poj.org/problem?id=2781
题目大意:编号从1~N的网络中,从c1走到c2同学的地方寻求帮助,求使得经过的中间站点最少。
解题思路:简单的最短路问题,两点之间的最短路径,故用SFPA。
范围1<=N<=105,不能用邻接矩阵,二维数组会爆栈,用邻接链表来处理.
time[i]数组记录走到i点是需要走多少个站点,当第一次走到b点就立刻退出.
time[b]-1既为中间经过的站点数目.
代码:
#include <stdio.h> #include <stdlib.h> #include <string.h> #define MAX 100001 #define INF 0x3f3f3f3f struct ArcNode{ int to; int weigh; struct ArcNode *next; }; struct ArcNode *listb[MAX]; int a,b,e,s,n,list[MAX*400],dist[MAX]={0},time[MAX]={0}; //time[]纪录到底此点是走了多少个站点 void SPFA(int v0) { int u,v; struct ArcNode *temp; s=e=0; list[e++]=v0; dist[v0]=1; time[v0]=0; while(e!=s) { u=list[s++]; dist[u]=0; temp=listb[u]; while(temp!=NULL) //访问邻接链表 { v=temp->to; if(dist[v]!=1) //***如果不在队列中则入队,没有此判断会 WA { list[e++]=v; time[v]=time[u]+1; //***time[v]是上点走的站点总数再 +1 dist[v]=1; } if(v==b) { return ; //第一次到达 b 就立刻退出 } temp=temp->next; } } } int main() { int i,j,m; struct ArcNode *temp; scanf("%d",&n); for(i=0;i<n;i++) { scanf("%d%d",&a,&m); for(j=0;j<m;j++) { scanf("%d",&b); temp=(struct ArcNode*)malloc(sizeof(struct ArcNode)); //构建邻接链表 temp->to=b; temp->weigh=1; temp->next=NULL; if(listb[a]==NULL) listb[a]=temp; else { temp->next=listb[a]; listb[a]=temp; } } } scanf("%d%d",&a,&b); SPFA(a); //从a点开始 SPFA printf("%d %d %d\n",a,b,time[b]-1); return 0; }
注:原创文章,转载请注明出处