POJ-3159-Candies-(差分约束，Dijkstra）

链接：https://vjudge.net/problem/POJ-3159

题意：

N个小孩，M个约束

以A，B，C给出。即小孩B的糖果不能比A多C以上。

思路：

差分约束：

若有 A-B <= V1,B-C <= V2,即A-C <= V1+V2。

用最短路求法求。

A->B = V1,B->C=V2,A->C=V3，则有A->C = min(A->C,(A->B+B->C))。

代码：

#include <iostream>

#include <memory.h>

#include <string>

#include <istream>

#include <sstream>

#include <vector>

#include <stack>

#include <algorithm>

#include <map>

#include <queue>

using namespace std;

const int MAXN = 150000+10;

const long long INF = 99999999;

typedef long long LL;

//邻接表存图优化Dijkstra算法

struct Node

{

    int _w;

    long long _v;

    bool operator < (const Node & that)const

    {

        return this->_v > that._v;

    }

    Node(int w,int v):_w(w),_v(v){}

};

int First[MAXN],Next[MAXN];

int u[MAXN],v[MAXN],w[MAXN];

int Dis[MAXN];

int Vis[MAXN];

int n,m;

void Read_Graph()

{

    scanf("%d%d",&n,&m);

    for (int e = 1;e <= m;e++)

    {

        scanf("%d%d%d",&u[e],&v[e],&w[e]);

    }

}

void Init()

{

    for (int i = 1;i<=m;i++)

        First[i] = -1;

    for (int e = 1;e <= m;e++)

    {

        Next[e] = First[u[e]];

        First[u[e]] = e;

    }

}

int Dijkstra()

{

    for (int i = 1;i <= n;i++)

    {

        Dis[i] = INF;

        Vis[i] = 0;

    }

    Dis[1] = 0;

    priority_queue<Node> que;

    que.push(Node(1,0));

    while (!que.empty())

    {

        if (Vis[que.top()._w] == 1)

            que.pop();

        else

        {

            int e = que.top()._w;

            Vis[e] = 1;

            e = First[e];

            while (e != -1)

            {

                if (Dis[v[e]] > Dis[u[e]] + w[e])

                {

                    Dis[v[e]] = Dis[u[e]] + w[e];

                    que.push(Node(v[e],Dis[v[e]]));

                }

                e = Next[e];

            }

            que.pop();

        }

    }

    return Dis[n];

}

int main()

{

    Read_Graph();

    Init();

    cout << Dijkstra() << endl;

    return 0;

}

巴特西

POJ-3159-Candies-(差分约束，Dijkstra）

链接：https://vjudge.net/problem/POJ-3159

题意：

思路：

代码：

最新文章

热门文章