Dijkstra_邻接表 Hlg 1419 昂贵的假花

呃~

一开始写了邻接矩阵的~结果mle了~

后来改成了邻接表的~结果tle了~

然后就用快排做了~~

但是程大学长说用堆排序~wulala~看着很麻烦吖~暂时放着~~

输入T<T组样例..>

输入n个點+m条边..

输入n个點的价值..

输入m条边<u 起点 v终点 w (u, v)的权值..>

其实最重要就是求单源最短路径了..

用邻接表可以解决点太多的问题..

用堆排序或优先队列可以解决 tle的问题..

AC代码<邻接表_优先排列>..

View Code

  1 #include <stdio.h>
  2 #include <cstring>
  3 #include <queue>
  4 using namespace std;
  5 #define INF 0x1f1f1f1f
  6 
  7 struct ArcNode
  8 {
  9 　　int adjvex;
 10 　　long long w;
 11 　　ArcNode *nextarc;
 12 }node[50010];
 13 
 14 struct Node
 15 {
 16 　　int num;
 17 　　long long w;
 18 　　bool operator < (Node n) const
 19 　　{
 20 　　　　return w > n.w;
 21 　　}
 22 }tem, tem1;
 23 
 24 long long dist[50010];
 25 int n, e;
 26 bool fflag;
 27 ArcNode edge[50010 * 2];
 28 int nE;
 29 
 30 void Dijkstra(int v0)
 31 {
 32 　　int i, j;
 33 　　ArcNode *p = &node[v0];
 34 　　ArcNode *pi = NULL;
 35 　　priority_queue<Node> Q;
 36 
 37 　　while(p != NULL)
 38 　　{
 39 　　dist[p->adjvex] = p->w;
 40 　　p = p->nextarc;
 41 　　}
 42 
 43 　　dist[v0] = 0;
 44 　　tem.num = v0;
 45 　　tem.w = 0;
 46 
 47 　　Q.push(tem);
 48 　　while(!Q.empty())
 49 　　{
 50 　　　　tem = Q.top();
 51 　　　　Q.pop();
 52 
 53 　　　　for(pi = node[tem.num].nextarc; pi != NULL; pi = pi->nextarc)
 54 　　　　{
 55 　　　　　　tem1.w = tem.w + pi->w;
 56 　　　　　　tem1.num = pi->adjvex;
 57 　　　　　　if(tem1.w <= dist[tem1.num])
 58 　　　　　　{
 59 　　　　　　　　dist[tem1.num] = tem1.w;
 60 　　　　　　　　Q.push(tem1);
 61 　　　　　　}
 62 　　　　}
 63 　　}
 64 
 65 }//Dijkstra
 66 
 67 
 68 int main()
 69 {
 70 　　int T;
 71 　　int i, j, k;
 72 　　int a, b;
 73 　　long long w;
 74 　　ArcNode *p;
 75 　　long long sum;
 76 　　long long W[50010];
 77 　　while(scanf("%d", &T) != EOF)
 78 　　while(T--)
 79 　　{
 80 　　　　sum = 0;
 81 　　　　fflag = true;
 82 　　　　scanf("%d%d", &n, &e);
 83 
 84 　　　　for(i = 1; i <= n; ++i)
 85 　　　　{
 86 　　　　　　scanf("%lld", &W[i]);
 87 　　　　　　node[i].nextarc = NULL;
 88 　　　　}// for i n cin W
 89 
 90 　　　　nE = 0;
 91 　　　　for(i = 0; i < e; ++i)
 92 　　　　{
 93 　　　　　　scanf("%d %d %lld", &a, &b, &w);
 94 
 95 　　　　　　p = edge + nE++;
 96 　　　　　　p->adjvex = b;
 97 　　　　　　p->w = w;
 98 　　　　　　p->nextarc = node[a].nextarc;
 99 　　　　　　node[a].nextarc = p;
100 
101 　　　　　　p = edge + nE++;
102 　　　　　　p->adjvex = a;
103 　　　　　　p->w = w;
104 　　　　　　p->nextarc = node[b].nextarc;
105 　　　　　　node[b].nextarc = p;
106 
107 　　　　}//for i v cin a b w
108 
109 　　　　memset(dist, INF, sizeof(dist));
110 
111 　　　　Dijkstra(1);
112 
113 　　　　for(i = 1; i <= n; ++i)
114 　　　　{
115 　　　　　　if(dist[i] >= INF)
116 　　　　　　{
117 　　　　　　　　fflag = false;
118 　　　　　　　　break;
119 　　　　　　}
120 　　　　}//for i n
121 
122 
123 　　　　if(!fflag)
124 　　　　{
125 　　　　　　printf("No Answer\n");
126 　　　　　　continue;
127 　　　　}//if !flag
128 　　　　else
129 　　　　{
130 　　　　　　for(i = 1; i <= n; ++i)
131 　　　　　　　　sum += dist[i]*W[i];
132 　　　　　　printf("%lld\n", sum);
133 　　　　}// flag
134 　　}//while t--
135 　　return 0;
136 }

Mle代码<邻接矩阵>

View Code

  1 #include<stdio.h>
  2 
  3 #include<cstring>
  4 
  5 #defineINF 0x7fffffff
  6 
  7 usingnamespace std;
  8 
  9  
 10 
 11 intn, e;
 12 
 13 intEdge[50010][50010];
 14 
 15 boolS[50010];
 16 
 17 intdist[50010];
 18 
 19  
 20 
 21 voidDijkstra(int v0)
 22 
 23 {
 24 
 25     int i, j, k;
 26 
 27     for(i = 0; i < n; ++i)
 28 
 29     {
 30 
 31         dist[i] = Edge[v0][i];
 32 
 33         S[i] = false;
 34 
 35     }// for i n
 36 
 37     S[v0] = true;
 38 
 39     dist[v0] = 0;
 40 
 41     for(i = 0; i < n-1; ++i)
 42 
 43     {
 44 
 45         int min = INF;
 46 
 47         int u = v0;
 48 
 49         for(j = 0; j < n; ++j)
 50 
 51         {
 52 
 53             if(!S[j] && dist[j] <min)
 54 
 55             {
 56 
 57                u = j;
 58 
 59                 min = dist[j];
 60 
 61             }// if !S & dist < min
 62 
 63         }// for j n
 64 
 65         S[u] = true;
 66 
 67  
 68 
 69         for(k = 0; k < n; ++k)
 70 
 71         {
 72 
 73             if(!S[k] && Edge[u][k] <INF && dist[u]+Edge[u][k] < dist[k])
 74 
 75             {
 76 
 77                 dist[k] = dist[u]+Edge[u][k];
 78 
 79             }// if !S  && Edge(u, k) ***
 80 
 81         }// for k n
 82 
 83     }//for i n-1
 84 
 85  
 86 
 87 }//Dijkstra v0
 88 
 89  
 90 
 91 intmain()
 92 
 93 {
 94 
 95     int T;
 96 
 97     int i, j, k;
 98 
 99     int W[50010];
100 
101     int a, b, w;
102 
103     long long sum;
104 
105     bool flag;
106 
107  
108 
109     while(scanf("%d", &T) != EOF)
110 
111     while(T--)
112 
113     {
114 
115         memset(Edge, 0, sizeof(Edge));
116 
117         flag = true;
118 
119         sum = 0;
120 
121         scanf("%d%d", &n,&e);
122 
123         for(i = 0; i < n; ++i)
124 
125         scanf("%d", &W[i]);
126 
127  
128 
129         for(i = 0; i < n; ++i)
130 
131         {
132 
133             for(j = 0; j < n; ++j)
134 
135             {
136 
137                 if(i == j) Edge[i][j] = 0;
138 
139                 else if(Edge[i][j] == 0)Edge[i][j] = INF;
140 
141             }//for j n
142 
143         }//for i n
144 
145  
146 
147         for(i = 0; i < e; ++i)
148 
149         {
150 
151             scanf("%d%d%d", &a,&b, &w);
152 
153             Edge[a-1][b-1] = w;
154 
155             Edge[b-1][a-1] = w;
156 
157         }// cin u v w
158 
159 /*
160 
161 for(i= 0; i < n; ++i)
162 
163 {
164 
165     for(j = 0; j < n; ++j)
166 
167     if(Edge[i][j] == INF) printf("*     ");
168 
169     else printf("%d     ", Edge[i][j]);
170 
171     puts("");
172 
173 }
174 
175 ///
176 
177         Dijkstra(0);
178 
179  
180 
181         for(i = 1; i < n; ++i)
182 
183         if(dist[i] == INF)
184 
185         {
186 
187             flag = false;
188 
189             break;
190 
191         }//for no answer
192 
193         if(!flag)
194 
195         {
196 
197             printf("No Answer\n");
198 
199             continue;
200 
201         }//cout no answer
202 
203         else
204 
205         {
206 
207             for(i = 1; i < n; ++i)
208 
209             {
210 
211                 sum += dist[i]*W[i];
212 
213             }// for i n-1
214 
215  
216 
217             printf("%lld\n", sum);
218 
219         }// cout sum
220 
221  
222 
223     }// while t--
224 
225  
226 
227     return 0;
228 
229 }
230 
231

Tle代码<邻接表..>

View Code

  1 #include<stdio.h>
  2 
  3 #include<cstring>
  4 
  5 #include<queue>
  6 
  7 #defineINF 0x1f1f1f1f
  8 
  9  
 10 
 11 structArcNode
 12 
 13 {
 14 
 15     ArcNode(){nextarc = NULL;}
 16 
 17     int adjvex;
 18 
 19     long long w;
 20 
 21     ArcNode *nextarc;
 22 
 23 }node[50010];
 24 
 25  
 26 
 27 longlong dist[50010];
 28 
 29 boolflag[50010];
 30 
 31 intn, e;
 32 
 33 boolfflag;
 34 
 35  
 36 
 37 voidDijkstra(int v0)
 38 
 39 {
 40 
 41     int i, j;
 42 
 43     ArcNode *p = &node[v0];
 44 
 45     ArcNode *pi = NULL;
 46 
 47  
 48 
 49     memset(flag, false, sizeof(flag));
 50 
 51  
 52 
 53     while(p != NULL)
 54 
 55     {
 56 
 57         dist[p->adjvex] = p->w;
 58 
 59         p = p->nextarc;
 60 
 61     }
 62 
 63     flag[v0] = true;
 64 
 65     dist[v0] = 0;
 66 
 67     for(i = 0; i < n-1; ++i)   
 68 
 69     {
 70 
 71         long long min = INF, u = v0;
 72 
 73         for(j = 1; j <= n; ++j)
 74 
 75         {
 76 
 77             if(!flag[j] && dist[j] <min)
 78 
 79             {
 80 
 81                 u = j;
 82 
 83                 min = dist[j];
 84 
 85             }//if !flag && dist <min
 86 
 87         }// for j n
 88 
 89  
 90 
 91         flag[u] = true;
 92 
 93         for(pi = &node[u]; pi; pi =pi->nextarc)
 94 
 95         {
 96 
 97             if(!flag[pi->adjvex] &&dist[u]+pi->w < dist[pi->adjvex])
 98 
 99             {
100 
101                 dist[pi->adjvex] = dist[u] +pi->w;
102 
103             }
104 
105         }
106 
107     }// for i n-1
108 
109 }//Dijkstra
110 
111  
112 
113  
114 
115 intmain()
116 
117 {
118 
119     int T;
120 
121     int i, j, k;
122 
123     int a, b;
124 
125     long long w;
126 
127     ArcNode *p;
128 
129     long long sum;
130 
131     long long W[50010];
132 
133     while(scanf("%d", &T) != EOF)
134 
135     while(T--)
136 
137     {
138 
139         sum = 0;
140 
141         fflag = true;
142 
143         scanf("%d%d", &n,&e);
144 
145  
146 
147         for(i = 1; i <= n; ++i)
148 
149         {
150 
151             scanf("%lld", &W[i]);
152 
153             node[i].nextarc = NULL;
154 
155         }// for i n cin W
156 
157         for(i = 0; i < e; ++i)
158 
159         {
160 
161             scanf("%d %d %lld",&a, &b, &w);
162 
163  
164 
165             p = new ArcNode;
166 
167             p->adjvex = b;
168 
169             p->w = w;
170 
171             p->nextarc = node[a].nextarc;
172 
173             node[a].nextarc = p;
174 
175  
176 
177             p = new ArcNode;
178 
179             p->adjvex = a;
180 
181             p->w = w;
182 
183             p->nextarc = node[b].nextarc;
184 
185             node[b].nextarc = p;
186 
187  
188 
189  
190 
191         }//for i v cin a b w
192 
193  
194 
195         memset(dist, INF, sizeof(dist));
196 
197  
198 
199         Dijkstra(1);
200 
201  
202 
203         for(i = 1; i <= n; ++i)
204 
205         {
206 
207             if(dist[i] >= INF)
208 
209             {
210 
211                 fflag = false;
212 
213                 break;
214 
215             }
216 
217         }//for i n
218 
219  
220 
221  
222 
223         if(!fflag)
224 
225         {
226 
227             printf("No Answer\n");
228 
229             continue;
230 
231         }//if !flag
232 
233         else
234 
235         {
236 
237             for(i = 1; i <= n; ++i)
238 
239             sum += dist[i]*W[i];
240 
241             printf("%lld\n", sum);
242 
243         }// flag
244 
245     }//while t--
246 
247     return 0;
248 
249 }
250 
251

黄李龙学长版~<堆排序>

View Code

  1 #include <cstdio>
  2 
  3 #include <cstring>
  4 
  5 #include <climits>
  6 
  7 #include <iostream>
  8 
  9 #include <algorithm>
 10 
 11 using namespace std;
 12 
 13 typedef long long llong;
 14 
 15 const int MAXN = 50000 + 10;
 16 
 17  
 18 
 19 struct Edge {
 20 
 21        intto, len;
 22 
 23        Edge*next;
 24 
 25 };
 26 
 27 int nE;
 28 
 29 Edge *head[MAXN];
 30 
 31 Edge E[MAXN * 2];
 32 
 33  
 34 
 35 void addEdge(int u, int v, int len)
 36 
 37 {
 38 
 39        Edge*e = E + nE++;
 40 
 41        e->to= v;
 42 
 43        e->len= len;
 44 
 45        e->next= head[u];
 46 
 47        head[u]= e;
 48 
 49 }
 50 
 51  
 52 
 53 bool vis[MAXN];
 54 
 55 struct Node {
 56 
 57        intv;
 58 
 59        llonglen;
 60 
 61        booloperator < (const Node &B) const {
 62 
 63               returnlen > B.len;
 64 
 65        }
 66 
 67 } vHeap[MAXN];
 68 
 69  
 70 
 71 void dijkstra(int n, int s, Edge *head[],llong len[])
 72 
 73 {
 74 
 75        memset(vis,0, sizeof(vis[0]) * (n + 1));
 76 
 77        memset(len,-1, sizeof(len[0]) * (n + 1));
 78 
 79        len[s]= 0;
 80 
 81        intcnt = 1;
 82 
 83        vHeap[0].v= s;
 84 
 85        vHeap[0].len= 0;
 86 
 87        for(int i = 0; i < n; ++i) {
 88 
 89               intu = -1;
 90 
 91               llongminLen = -1;
 92 
 93               while(cnt > 0) {
 94 
 95                      u= vHeap[0].v;
 96 
 97                      minLen= vHeap[0].len;
 98 
 99                      pop_heap(vHeap,vHeap + cnt);
100 
101                      --cnt;
102 
103                      if(!vis[u]) {
104 
105                             break;
106 
107                      }
108 
109                      u= -1;
110 
111               }
112 
113               if(u == -1) break;
114 
115               vis[u]= true;
116 
117               for(Edge *e = head[u]; e; e = e->next) {
118 
119                      if(!vis[e->to] && (len[e->to] == -1 || len[e->to] > minLen +e->len)) {
120 
121                             len[e->to]= minLen + e->len;
122 
123                             vHeap[cnt].v= e->to;
124 
125                             vHeap[cnt].len= len[e->to];
126 
127                             ++cnt;
128 
129                             push_heap(vHeap,vHeap + cnt);
130 
131                      }
132 
133               }
134 
135        }
136 
137 }
138 
139  
140 
141 int weight[MAXN];
142 
143 llong len[MAXN];
144 
145  
146 
147 int main()
148 
149 {
150 
151        intnTest;
152 
153        intn, e;
154 
155        scanf("%d",&nTest);
156 
157        while(nTest--) {
158 
159               scanf("%d%d", &n, &e);
160 
161               for(int i = 1; i <= n; ++i) {
162 
163                      scanf("%d",&weight[i]);
164 
165               }
166 
167               nE= 0;
168 
169               memset(head,0, sizeof(head));
170 
171               for(int i = 0; i < e; ++i) {
172 
173                      inta, b, w;
174 
175                      scanf("%d%d %d", &a, &b, &w);
176 
177                      addEdge(a,b, w);
178 
179                      addEdge(b,a, w);
180 
181               }
182 
183  
184 
185               dijkstra(n,1, head, len);
186 
187               llongans = 0;
188 
189               for(int i = 1; i <= n; ++i) {
190 
191                      if(len[i] < 0) {
192 
193                             ans= -1;
194 
195                             break;
196 
197                      }
198 
199                      ans+= weight[i] * len[i];
200 
201               }
202 
203               if(ans >= 0) {
204 
205                      printf("%lld\n",ans);
206 
207               }else {
208 
209                      puts("NoAnswer");
210 
211               }
212 
213        }
214 
215        return0;
216 
217 }