洛谷 [USACO05DEC] 布局 题解

今天学了差分约束系统， 这是一道板子题。

核心：a[v]>a[u]+d 相当于从u到v连一条长度为d的有向边。由于要判断有环，所以要从0点先跑一遍spfa因为1点不一定能到所有的点。

 1 #include
 2 #include
 3 #include
 4 #include
 5 #include
 6 #define INF 2139062143
 7 #define maxn 1005
 8 #define maxm 40005
 9 using namespace std;
10 int n,ml,md,a,b,d;
11 struct node
12 {
13     int u,v,w,nex;
14 }edge[maxm];
15 int head[maxn],cnt=0;
16 queue<int> q;
17 int vis[maxn],dis[maxn],circle[maxn];
18 inline int read() 
19 {
20     int x=0;
21     bool f=1;
22     char c=getchar();
23     for(; !isdigit(c); c=getchar()) if(c=='-') f=0;
24     for(; isdigit(c); c=getchar()) x=(x<<3)+(x<<1)+c-'0';
25     if(f) return x;
26     return 0-x;
27 }
28 inline void add(int x,int y,int z)
29 {
30     cnt++;
31     edge[cnt].u=x;
32     edge[cnt].v=y;
33     edge[cnt].w=z;
34     edge[cnt].nex=head[x];
35     head[x]=cnt;
36 }
37 inline void spfa(int s)
38 {
39     memset(dis,127,sizeof(dis));
40     memset(circle,0,sizeof(circle));
41     q.push(s);
42     vis[s]=1;dis[s]=0;
43     circle[s]++;
44     while(!q.empty())
45     {
46         int now=q.front();
47         q.pop();
48         vis[now]=0;
49         for(int i=head[now];i;i=edge[i].nex)
50         {
51             int to=edge[i].v;
52             if(dis[now]+edge[i].w<dis[to])
53             {
54                 dis[to]=dis[now]+edge[i].w;
55                 if(!vis[to])
56                 {
57                     vis[to]=1;
58                     q.push(to);
59                     circle[to]++;
60                     if(circle[to]>=n)
61                     {
62                         cout<<-1;
63                         exit(0);
64                     }
65                 }
66             }
67         }
68     }
69 }
70 int main()
71 {
72     n=read();ml=read();md=read();
73     for(int i=1;i<=n;i++)add(0,i,0);
74     for(int i=1;i<=ml;i++)
75     {
76         a=read();b=read();d=read();
77         add(a,b,d);
78     }
79     for(int i=1;i<=md;i++)
80     {
81         a=read();b=read();d=read();
82         add(b,a,-d);
83     }
84     spfa(0);
85     spfa(1);
86     if(dis[n]==INF)cout<<-2;
87     else printf("%d",dis[n]);
88     return 0;
89 }

请各位大佬斧正（反正我不认识斧正是什么意思）