Candies(差分约束)

题意：

flymouse是幼稚园班上的班长，一天老师给小朋友们买了一堆的糖果，由flymouse来分发，在班上，
flymouse和snoopy是死对头，两人势如水火，不能相容，因此fly希望自己分得的糖果数尽量多于
snoopy，而对于其他小朋友而言，则只希望自己得到的糖果不少于班上某某其他人就行了。

比如A小朋友强烈希望自己的糖果数不能少于B小朋友m个，即B- A<=m，A，B分别为
A、B小朋友的分得的糖果数。这样给出若干组这样的条件，要使fly最后分得的糖果数s1和snoopy
最后分得的糖果数s2差别取到最大！即s2-s1取最大.

思路：求源点1到n的最短距离。Dijstra+邻接表

不过直接用dij会超时。可以用优先队列优化一下。不过运算符重载那里被卡了好久。悲惨的教训啊。

 #include<stdio.h>

 #include<string.h>

 #include<queue>

 using namespace std;

 const int INF = 0x3f3f3f3f;

 const int maxv = ;

 const int maxe = ;

 struct node

 {

     int v,w,next;

 }edge[maxe];//邻接表

 struct node1

 {

     int v,c;

     bool operator < (const node1 &t) const

     {

         return c > t.c;//距离从小到大排序

     }

 };//存每个节点和它到源点的最短距离。

 int n,m,cnt;

 int p[maxe];

 int dis[maxv];

 int vis[maxv];

 void add(int u, int v, int w)

 {

     cnt++;

     edge[cnt].v = v;

     edge[cnt].w = w;

     edge[cnt].next = p[u];

     p[u] = cnt;

 }

 void dijstra(int s)

 {

     priority_queue<struct node1> que;

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

         dis[i] = INF;

     memset(vis,,sizeof(vis));

     dis[s] = ;

     que.push((struct node1){s,dis[s]});

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

     {

         while(!que.empty() && vis[que.top().v])

             que.pop();

         if(que.empty()) break;

         node1 tmp = que.top();

         que.pop();

         vis[tmp.v] = ;

         for(int j = p[tmp.v]; j; j = edge[j].next)

         {

             if((dis[edge[j].v] > dis[tmp.v] + edge[j].w) && !vis[edge[j].v])

             {

                 dis[edge[j].v] = dis[tmp.v] + edge[j].w;

                 que.push((struct node1){edge[j].v,dis[edge[j].v]});

             }

         }

     }

 }

 int main()

 {

     while(~scanf("%d %d",&n,&m))

     {

         int u,v,w;

         memset(p,,sizeof(p));

         cnt = ;

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

         {

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

             add(u,v,w);

         }

         dijstra();

         printf("%d\n",dis[n]);

     }

     return ;

 }

看discuss里面也可以用SPFA+stack，可能用stack效率高一点吧。

 #include<stdio.h>

 #include<string.h>

 #include<algorithm>

 #include<stack>

 using namespace std;

 const int INF = 0x3f3f3f3f;

 const int maxv = ;

 const int maxe = ;

 struct node

 {

     int v,w;

     int next;

 }edge[maxe];

 int n,m,cnt;

 int p[maxe];

 int dis[maxv],instack[maxv];

 void add(int u, int v, int w)

 {

     cnt++;

     edge[cnt].v = v;

     edge[cnt].w = w;

     edge[cnt].next = p[u];

     p[u] = cnt;

 }

 void SPFA(int s)

 {

     stack<int>st;

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

         dis[i] = INF;

     memset(instack,,sizeof(instack));

     dis[s] = ;

     st.push(s);

     instack[s] = ;

     while(!st.empty())

     {

         int u = st.top();

         st.pop();

         instack[u] = ;

         for(int i = p[u]; i; i = edge[i].next)

         {

             if(dis[edge[i].v] > dis[u] + edge[i].w)

             {

                 dis[edge[i].v] = dis[u] + edge[i].w;

                 if(!instack[edge[i].v])

                 {

                     st.push(edge[i].v);

                     instack[edge[i].v] = ;

                 }

             }

         }

     }

 }

 int main()

 {

     while(~scanf("%d %d",&n,&m))

     {

         cnt = ;

         memset(p,,sizeof(p));

         int u,v,w;

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

         {

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

             add(u,v,w);

         }

         SPFA();

         printf("%d\n",dis[n]);

     }

     return ;

 }