今天学了差分约束系统, 这是一道板子题。
核心:a[v]>a[u]+d 相当于从u到v连一条长度为d的有向边。由于要判断有环,所以要从0点先跑一遍spfa因为1点不一定能到所有的点。
#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<queue>
#define INF 2139062143
#define maxn 1005
#define maxm 40005
using namespace std;
int n,ml,md,a,b,d;
struct node
{
int u,v,w,nex;
}edge[maxm];
int head[maxn],cnt=;
queue<int> q;
int vis[maxn],dis[maxn],circle[maxn];
inline int read()
{
int x=;
bool f=;
char c=getchar();
for(; !isdigit(c); c=getchar()) if(c=='-') f=;
for(; isdigit(c); c=getchar()) x=(x<<)+(x<<)+c-'';
if(f) return x;
return -x;
}
inline void add(int x,int y,int z)
{
cnt++;
edge[cnt].u=x;
edge[cnt].v=y;
edge[cnt].w=z;
edge[cnt].nex=head[x];
head[x]=cnt;
}
inline void spfa(int s)
{
memset(dis,,sizeof(dis));
memset(circle,,sizeof(circle));
q.push(s);
vis[s]=;dis[s]=;
circle[s]++;
while(!q.empty())
{
int now=q.front();
q.pop();
vis[now]=;
for(int i=head[now];i;i=edge[i].nex)
{
int to=edge[i].v;
if(dis[now]+edge[i].w<dis[to])
{
dis[to]=dis[now]+edge[i].w;
if(!vis[to])
{
vis[to]=;
q.push(to);
circle[to]++;
if(circle[to]>=n)
{
cout<<-;
exit();
}
}
}
}
}
}
int main()
{
n=read();ml=read();md=read();
for(int i=;i<=n;i++)add(,i,);
for(int i=;i<=ml;i++)
{
a=read();b=read();d=read();
add(a,b,d);
}
for(int i=;i<=md;i++)
{
a=read();b=read();d=read();
add(b,a,-d);
}
spfa();
spfa();
if(dis[n]==INF)cout<<-;
else printf("%d",dis[n]);
return ;
}
请各位大佬斧正