首页 > 代码库 > [SPFA][jzyzoj1220]第二短路
[SPFA][jzyzoj1220]第二短路
题面就不给了= =就是求从1到n的第二短路
因为从1到1的路径还要再求一次,所以不能用dijkstra的方法进行松弛,这时候需要我们使用spfa
以下是策略:
1、当前求得最短路小于已知最短路时,先将第二短路进行更新(需要将新的第二短路和旧的最短路进行比较),再将第一短路进行更新;
2、当前求得最短路等于已知最短路时,将第二短路进行更新(需要将新的第二短路与旧的第二短路进行比较);
3、当前求得最短路大于已知最短路时,将第二短路进行更新(将求得最短路与第二短路进行比较);
其余部分就是SPFA的模板了,代码如下:
1 #include<iostream> 2 #include<cstdio> 3 #include<cstring> 4 using namespace std; 5 struct edge{ 6 int y,ne,v; 7 }edge[200010]; 8 int d1[5010],d2[5010],n,m,head[5010],len=0,queue[200010]; 9 bool vis[5010]; 10 inline void addedge(int x,int y,int v) 11 {edge[++len].y=y; edge[len].v=v; edge[len].ne=head[x]; head[x]=len;} 12 void init() 13 { 14 memset(head,-1,sizeof(head)); 15 scanf("%d%d",&n,&m); 16 int x,y,v; 17 for (int i=1;i<=m;i++) 18 { 19 scanf("%d%d%d",&x,&y,&v); 20 addedge(x,y,v); 21 addedge(y,x,v); 22 } 23 } 24 25 void spfa() 26 { 27 memset(d1,0x3f,sizeof(d1)); 28 memset(d2,0x3f,sizeof(d2)); 29 memset(vis,false,sizeof(vis)); 30 int Head=0,tail=1; 31 queue[1]=1; d1[1]=0; vis[1]=true; 32 while (Head<tail) 33 { 34 int tn=queue[++Head]; 35 int te=head[tn]; 36 vis[tn]=false; 37 for (int i=te;i!=-1;i=edge[i].ne) 38 { 39 int temp=edge[i].y; 40 if (d1[temp]>d1[tn]+edge[i].v) 41 { 42 d2[temp]=min(d1[temp],d2[tn]+edge[i].v); 43 d1[temp]=d1[tn]+edge[i].v; 44 if (!vis[temp]) 45 { 46 vis[temp]=true; 47 queue[++tail]=temp; 48 } 49 } 50 else 51 { 52 if (d1[temp]==d1[tn]+edge[i].v) 53 { 54 d2[temp]=min(d2[tn]+edge[i].v,d2[temp]); 55 if (!vis[temp]) 56 { 57 vis[temp]=true; 58 queue[++tail]=temp; 59 } 60 } 61 else if (d2[temp]>d1[tn]+edge[i].v) 62 { 63 d2[temp]=min(d1[tn]+edge[i].v,d2[temp]); 64 if (!vis[temp]) 65 { 66 vis[temp]=true; 67 queue[++tail]=temp; 68 } 69 } 70 } 71 } 72 } 73 printf("%d\n",d2[n]); 74 } 75 76 int main() 77 { 78 //freopen("add.in","r",stdin); 79 //freopen("add.out","w",stdout); 80 init(); 81 spfa(); 82 return 0; 83 }
[SPFA][jzyzoj1220]第二短路
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。