POJ 3159 Candies-白红宇的个人博客

POJ 3159 Candies

发布日期：2022-03-15 04:11:21 浏览次数：37 分类：技术文章

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

　　题意是给A和B发糖果，B的糖果数 – A的糖果数 <= c, 也就是B <= A + c，最后求n比1最多多

几个糖果。题目只有这一个约束条件，建图不难。将AB看成有向图的边，然后c看成边的权值，转化成

最短路来求解，大牛们都说了SPFA + queue会超时，所以用了SPFA + stack。因为这道题没有负

权的边，也可以用堆优化的dij来求这个最短路。

SPFA + Stack

/*Accepted    2396K    532MS    C++    1363B    2012-08-06 15:32:00*/#include
     
      #include
      
       #include
       
        const int inf = 0x3f3f3f3f;const int V = 30005;const int E = 150005;int pnt[E], cost[E], nxt[E];int head[V], e, dist[V];bool vis[V];int relax( int u, int v, int c){    if( dist[v] > dist[u] + c) {        dist[v] = dist[u] + c;        return 1;    }    return 0;}void addedge( int u, int v, int c){    pnt[e] = v; cost[e] = c; nxt[e] = head[u]; head[u] = e ++;}int SPFA( int src, int n){    int i;    for(i = 1; i <= n; ++ i)    {         vis[i] = false; dist[i] = inf;    }    dist[src] = 0;    int S[E], top = 1;    S[0] = src; vis[src] = true;    while(top) {        int u, v;        u = S[ --top]; vis[u] = false;        for(i = head[u]; i != -1; i = nxt[i]) {            v = pnt[i];            if( 1 == relax( u, v, cost[i]) && !vis[v]) {                S[ top ++] = v; vis[v] = true;            }        }    }    return dist[n];}int main(){    int n, m;    while( scanf( "%d%d", &n, &m) == 2)    {        int a, b, c;        e = 0;        memset( vis, false, sizeof vis);        memset( head, -1, sizeof head);        while( m --)        {            scanf( "%d%d%d", &a, &b, &c);            addedge( a, b, c);        }        printf( "%d\n", SPFA( 1, n));    }    return 0;}

Dijkstra

/*Accepted    2392K    610MS    C++    1376B    2012-08-06 15:27:31*/#include
     
      #include
      
       #include
       
        #include
        
         using namespace std;const int MAXN = 30030, MAXM = 150150;const int inf = 0x3f3f3f3f;int first[MAXN], next[MAXM], v[MAXM], w[MAXM], dist[MAXN];int n, m, e;typedef pair
         
           pii;void addedge(int a, int b, int c){    v[e] = b, w[e] = c;    next[e] = first[a], first[a] = e ++;}void ReadGraph(){    int a, b, c;    e = 0;    memset(first, -1, sizeof first);    while(m --)    {        scanf("%d%d%d", &a, &b, &c);        addedge(a, b, c);    }}int Dijkstra(int src, int n){    int i, x;    pii u;    priority_queue
          
           , greater
           
             > q; for(i = 1; i <= n; i ++) dist[i] = inf; dist[src] = 0; q.push(make_pair(dist[src], src)); while(!q.empty()) { u = q.top(), q.pop(); x = u.second; if(dist[x] != u.first) continue; if(n == x) break; for(i = first[x]; i != -1; i = next[i]) { if(dist[v[i]] > dist[x] + w[i]) { dist[v[i]] = dist[x] + w[i]; q.push(make_pair(dist[v[i]], v[i])); } } } return dist[n];}int main(){ while(scanf("%d%d", &n, &m) == 2) { ReadGraph(); printf("%d\n", Dijkstra(1, n)); } return 0;}

转载于:https://www.cnblogs.com/Yu2012/archive/2012/08/06/2440719.html

转载地址：https://blog.csdn.net/weixin_30536513/article/details/99808409 如侵犯您的版权，请留言回复原文章的地址，我们会给您删除此文章，给您带来不便请您谅解！

上一篇：使用Logstash filter grok过滤日志文件

下一篇：canvas基本用法

发表评论

关于作者

喝酒易醉，品茶养心，人生如梦，品茶悟道，何以解忧？唯有杜康！

-- 愿君每日到此一游！

发表评论

最新留言

关于作者

推荐文章