poj 3159 Candies dijkstra + queue

题目链接：

题目大意：

　　飞天鼠是班长，一天班主任买了一大包糖果，要飞天鼠分发给大家，班里面有n个人，但是学生A认为学生B比自己多的糖果数目不应该大于c，如果不满足自己的条件，学生A就会向老师告状，在这个班级里面泰迪熊的编号是1，班长的编号是n，班长想和泰迪熊的糖果相差最大，问：在满足m个学生的要求后，班长与泰迪熊的糖果相差最大是多少？

解题思路：

　　差分约束系统，|Xa-Xb| <= c，我们假设Xa小于Xb，把糖果的最大差当成边权，因为要满足全部人的要求，也就是要求所建图的最短路，用spfa+queue优化tle了，然后我就用了dijkstra+优先队列。感觉用邻接表+优先队列对dijkstra优化真是太美妙了，省去了很多的无用枚举，但是dijkstra的先天不足还是没有办法挽救~~~~

 #include <cstdio>

 #include <cstring>

 #include <cstdlib>

 #include <queue>

 #include <vector>

 #include <iostream>

 #include <algorithm>

 using namespace std;

 #define maxn 30010

 struct Edge

 {

     int e, w;

     Edge(int e=, int w=) : e(e),w(w) {}

 };

 bool operator < (const Edge &a, const Edge &b)

 {

     return a.w > b.w;//dist小的优先级高

 }

 vector< vector<Edge> > G;//二维vector

 //vector<Edge>G[maxn]要比前者慢，估计申请空间需要的时间也比较可观

 bool vis[maxn];

 int n;

 void dijkstra();

 int main ()

 {

     int m;

     while (scanf ("%d %d", &n, &m) != EOF)

     {

         G.clear();

         G.resize(n+);//动态申请空间

         while (m --)

         {

             int a, b, s;

             scanf ("%d %d %d", &a, &b, &s);

             G[a].push_back(Edge(b, s));

         }

         dijkstra ();

     }

     return ;

 }

 void dijkstra()

 {

     priority_queue<Edge>Q;

     Edge p, q;

     memset (vis, false, sizeof(vis));

     p.e = , p.w = ;

     Q.push (p);

     while (!Q.empty())

     {

         p = Q.top();//选取最优点

         Q.pop();

         if (vis[p.e])//已求出最短路，进行下一个

             continue;

         if (p.e == n)//已求出1到n的最短路

             break;

         vis[p.e] = true;

         int len = G[p.e].size();

         for (int i=; i<len; i++)

         {

             q = G[p.e][i];

             if ( !vis[q.e] )//对剩余的点进行松弛操作

             {

                 q.w += p.w;

                 Q.push(q);

             }

         }

     }

     printf ("%d\n", p.w);

 }

巴特西

poj 3159 Candies dijkstra + queue

最新文章

热门文章