poj 3159 Candies (差分约束)

 1 http://poj.org/problem?id=3159 


 有一批糖果要由班长flymouse分发给班里的小朋友，
给出m对数据u,v,w，表示第v个小朋友最多比第u个小朋友多w个，
但flymouse与snoopy不和，所以在满足上述约束的条件下，
flymouse要尽量比snoopy多。snoopy标号1，flymouse标号n

/*
 2 终于 把这道题过了 ，wa了n次，spfa+队列 会 超时，tmd，改了 spfa+stack
 3  spfa差分约束，dis[i]为第i人得到的糖果数目。对于每个约束管理就能列出不等式：
 4  dis[a]>=dis[b]-c，就能转化为dis[b]<=dis[a]+c。也就是差分约束最短路中的三角不等式。
 5  又由于这里求的是第n点与第1个点的关系，所以就把1设为最短路中的其实点而不舍虚拟起始点。
 6  按照这个关系建出图求出最短路，则dis[n]就是答案。
 7 */
 8 
 9 #include<cstdio>
10 #include<istream>
11 #include<cstring>
12 
13 #define N 400000
14 using namespace std;
15 const int inf=1<<28;
16 struct node
17 {
18     int y;
19     int w;
20     int next;
21 }p[N*20];
22 int n,m,dis[N],vis[N],num,next[N];
23 int s[N];
24 void insert(int x,int y,int z)
25 {
26     p[num].y=y;
27     p[num].w=z;
28     p[num].next=next[x];
29     next[x]=num;
30     num++;
31 }
32 
33 void SPFA(int x)
34 {
35     int i;
36      memset(vis,0,sizeof(vis));
37     for(int i=0;i<=n;i++)dis[i]=inf;
38     dis[1]=0;
39     vis[1]=1;
40     int top=0;
41 
42     s[++top]=1;
43 
44     while(top)
45     {
46         int k=s[top--];
47 
48         vis[k]=0;
49         for(i=next[k];i!=0;i=p[i].next)
50         {
51             int a=p[i].y;
52             int len=p[i].w;
53             if(dis[a]>dis[k]+len)
54             {
55                 dis[a]=dis[k]+len;
56                 if(!vis[a])
57                 {
58                     vis[a]=1;
59                     s[++top]=a;
60 
61                 }
62             }
63         }
64 
65     }
66 }
67 int main()
68 {
69     int i,x,y,z;
70       while(scanf("%d%d",&n,&m)!=EOF)
71       {
72 
73 
74       memset(next,0,sizeof(next));
75       num=1;
76       for(i=1;i<=m;i++)
77       {
78           scanf("%d%d%d",&x,&y,&z);
79           insert(x,y,z);
80       }
81       SPFA(1);
82       printf("%d\n",dis[n]);
83       }
84 }