1 #include<iostream> 2 #include<cstring> 3 #include<cstdio> 4 #include<queue> 5 #define MAX 9999999 6 7 using namespace std; 8 9 struct node { 10 int v,w;//v终点，w权值 11 int nest;//下一个 12 }; 13 node edge[150000];//前向星 每个元素即每条边 14 int head[25030];//头指针式的数组 即邻接链表的指针数组 15 int dis[25010];//保存每点最短距离 16 int flag[25010];//保存某点加入队列的次数 17 bool vis[25010];//标记数组 18 int cnt;//下标 19 20 21 void add(int u,int v,int w)//加边 22 { 23 edge[cnt].v=v; 24 edge[cnt].w=w; 25 edge[cnt].nest=head[u];//相当于链表头插入法 26 head[u]=cnt++; // 27 } 28 29 bool SPFA(int s,int t) 30 { 31 int i,u,v;//u从Q中取出的点 v找到的点 32 deque<int> que;//双向队列 33 34 fill(dis,dis+t+1,MAX); 35 memset(flag,0,sizeof(flag)); 36 memset(vis,false,sizeof(vis)); 37 dis[s]=0;//s为? 即s为起点 38 que.push_back(s);//将s加入队列 39 while(!que.empty()) //队列不为空 40 { 41 42 u=que.front();//队列中取出 43 que.pop_front();//删除 44 vis[u]=false;//标记为未访问 45 for(i=head[u];i!=-1;i=edge[i].nest) //对所有与该点相邻的边进行查找 46 { 47 v=edge[i].v; 48 if(dis[v]>dis[u]+edge[i].w) 49 { 50 dis[v]=dis[u]+edge[i].w;//松弛成功 51 if(!vis[v])// 表示未标记 52 { 53 vis[v]=true;//标记 54 //flag[v]++;//表示该点进入队列的次数 55 //if(flag[v]>=n)//若该点进入队列次数超过n次 说明有负环 56 //return true;//返回有负环 57 //以下为SLF优化 58 if(!que.empty()&&dis[v]<dis[que.front()]) //若为队列为空&&队列队首元素距离大于当前点的距离 59 que.push_front(v);//加入到队首 60 else 61 que.push_back(v); 62 } 63 } 64 } 65 } 66 67 return true;//没有负环 68 } 69 70 int main() 71 { 72 int t,r,p,s,u,v,w,i; 73 74 scanf("%d%d%d%d",&t,&r,&p,&s); 75 memset(head,-1,sizeof(head)); 76 cnt=0; 77 while(r--) 78 { 79 scanf("%d%d%d",&u,&v,&w); 80 add(u,v,w); add(v,u,w); //双向无向图 81 } 82 while(p--) 83 { 84 scanf("%d%d%d",&u,&v,&w); 85 add(u,v,w); 86 } 87 SPFA(s,t); 88 for(i=1;i<=t;i++) 89 { 90 if(dis[i]>=MAX) 91 printf("NO PATH "); 92 else 93 printf("%d ",dis[i]); 94 } 95 return 0; 96 } 97
刚开始把数组开下了，得了30分，上网上找了个题解，感觉和我的一样 ，提交上之后正好通过，之后我又看了题，粗心。