HDU4725 SPFA (最短路+层级建图)
问题描述 ? ? ? 如果是每个点向比他层级小一或大一的点连边的话,复杂度为n××2,所以说每层抽象一个点,每层的抽象出来的点先此层的点连边,以此就避免的枚举每个点的层数 坑点: 同层之间的点不连通 ? 1 #include <cstdio> 2 #include <cmath> 3 #include <cstring> 4 #include <cstdlib> 5 #include <climits> 6 #include <ctype.h> 7 #include <queue> 8 #include <stack> 9 #include <vector> 10 #include <deque> 11 #include <set> 12 #include <map> 13 #include <iostream> 14 #include <algorithm> 15 using namespace std; 16 #define pi acos(-1.0) 17 #define INF 0x3f3f3f3f 18 #define N 200017 19 int n,m,k,c; 20 int Edgehead[N],dis[N]; 21 int vv[N],lay[N]; 22 struct 23 { 24 int v,w,next; 25 } Edge[20*N]; 26 bool vis[N]; 27 int cont[N]; 28 29 void init() 30 { 31 memset(Edgehead,0,sizeof(Edgehead)); 32 memset(vv,sizeof(vv)); 33 } 34 35 void Addedge(int u,int v,int w) 36 { 37 Edge[k].next = Edgehead[u]; 38 Edge[k].w = w; 39 Edge[k].v = v; 40 Edgehead[u] = k++; 41 } 42 int SPFA( int start) 43 { 44 queue<int>Q; 45 while(!Q.empty()) Q.pop(); 46 for(int i = 1 ; i <= N ; i++ ) 47 dis[i] = INF; 48 dis[start] = 0; 49 //++cont[start]; 50 memset(vis,false,sizeof(vis)); 51 vis[start] = 1; 52 Q.push(start); 53 while(!Q.empty())//直到队列为空 54 { 55 int u = Q.front(); 56 Q.pop(); 57 vis[u] = false; 58 for(int i = Edgehead[u] ; i!=-1 ; i = Edge[i].next)//注意 59 { 60 int v = Edge[i].v; 61 int w = Edge[i].w; 62 if(dis[v] > dis[u] + w) 63 { 64 dis[v] = dis[u]+w; 65 if( !vis[v] )//防止出现环,也就是进队列重复了 66 { 67 Q.push(v); 68 vis[v] = true; 69 } 70 //if(++cont[v] > n)//有负环 71 // return -1; 72 } 73 } 74 } 75 return dis[n]; 76 } 77 int main() 78 { 79 int u,v,w; 80 int t; 81 int cas = 0; 82 scanf("%d",&t); 83 while(t--) 84 { 85 init(); 86 scanf("%d%d%d",&n,&m,&c); 87 k = 1; 88 memset(Edgehead,-1,sizeof(Edgehead)); 89 90 for(int i = 1; i <= n; i++) 91 { 92 scanf("%d",&u);//i 在第u层 93 lay[i] = u; 94 vv[u] = 1; 95 } 96 97 for(int i = 1; i < n; i++) 98 { 99 if(vv[i] && vv[i+1]) //两层都出现过点相邻层才建边 100 { 101 Addedge(n+i,n+i+1,c); 102 Addedge(n+i+1,n+i,c); 103 } 104 } 105 106 for(int i = 1; i <= n; i++) //层到点建边 点到相邻层建边 107 { 108 Addedge(n+lay[i],i,0); 109 110 111 if(lay[i] > 1) 112 Addedge(i,n+lay[i]-1,c); 113 if(lay[i] < n) 114 Addedge(i,n+lay[i]+1,c); 115 116 117 } 118 119 for(int i = 1 ; i <= m ; i++ ) 120 { 121 scanf("%d%d%d",&u,&v,&w); 122 Addedge(u,w);//双向链表 123 Addedge(v,u,w);//双向链表 124 } 125 int s = SPFA(1);//从点1开始寻找最短路 126 if(s == INF) 127 { 128 s = -1; 129 } 130 printf("Case #%d: %dn",++cas,s); 131 } 132 return 0; 133 } (编辑:李大同) 【声明】本站内容均来自网络,其相关言论仅代表作者个人观点,不代表本站立场。若无意侵犯到您的权利,请及时与联系站长删除相关内容! |