SPFA/Dijkstra POJ 3159 Candies-白红宇

SPFA/Dijkstra POJ 3159 Candies

阅读量：6511 次

发布时间：2019-06-24

本文共 2143 字，大约阅读时间需要 7 分钟。

题意：n个人发糖果，B 比 A 多Ｃ的糖果，问最后第n个人比第一个人多多少的糖果

分析：最短路，Dijkstra 优先队列优化可过，SPFA竟然要用栈，队列超时！

代码：

/************************************************* Author        :Running_Time* Created Time  :2015-9-1 19:18:52* File Name     :POJ_3159.cpp ************************************************/#include 
     
      #include 
      
       #include 
       
        #include 
        
         #include 
         
          #include 
          
           #include 
           
            #include 
            
             #include 
             
              #include 
              
               #include 
               
                #include 
                
                 #include 
                 #include 
                  
                   #include 
                   
                    #include 
                    
                     #include 
                     
                      using namespace std;#define lson l, mid, rt << 1#define rson mid + 1, r, rt << 1 | 1typedef long long ll;const int N = 3e4 + 10;const int E = 150000 + 10;const int INF = 0x3f3f3f3f;const int MOD = 1e9 + 7;struct Edge { int v, w, nex; Edge (int _v = 0, int _w = 0) : v (_v), w (_w) {} bool operator < (const Edge &r) const { return w > r.w; }}edge[E];int d[N];int head[N];int vis[N];int cnt[N];int n, m, e;void init(void) { memset (head, -1, sizeof (head)); e = 0;}void Dijkstra(int s) { memset (vis, false, sizeof (vis)); for (int i=1; i<=n; ++i) d[i] = INF; d[s] = 0; priority_queue
                      
                        Q; Q.push (Edge (s, 0)); while (!Q.empty ()) { int u = Q.top ().v; Q.pop (); if (vis[u]) continue; vis[u] = true; for (int i=head[u]; ~i; i=edge[i].nex) { int v = edge[i].v, w = edge[i].w; if (!vis[v] && d[v] > d[u] + w) { d[v] = d[u] + w; Q.push (Edge (v, d[v])); } } }}void SPFA(int s) { memset (vis, false, sizeof (vis)); memset (d, INF, sizeof (d)); d[s] = 0; vis[s] = true; stack
                       
                         S; S.push (s); while (!S.empty ()) { int u = S.top (); S.pop (); vis[u] = false; for (int i=head[u]; ~i; i=edge[i].nex) { int v = edge[i].v, w = edge[i].w; if (d[v] > d[u] + w) { d[v] = d[u] + w; if (!vis[v]) { vis[v] = true; S.push (v); } } } }}void add_edge(int u, int v, int w) { edge[e].v = v, edge[e].w = w; edge[e].nex = head[u]; head[u] = e++;}int main(void) { while (scanf ("%d%d", &n, &m) == 2) { init (); for (int u, v, w, i=1; i<=m; ++i) { scanf ("%d%d%d", &u, &v, &w); add_edge (u, v, w); } //Dijkstra (1); SPFA (1); printf ("%d\n", d[n]); } return 0;}

转载于:https://www.cnblogs.com/Running-Time/p/4776758.html

你可能感兴趣的文章