本文共 1657 字，大约阅读时间需要 5 分钟。

$n$个人排队

$x$个相互喜欢的关系,表示$dis[u]-dis[v]<=w$

$y$个相互厌恶的关系,表示$dis[u]-dis[v]>=w$

$dis[u]<=dis[v]+w$

那么$v$向$u$连一条权值$w$的边

$dis[v]<=dis[u]-w$

那么$u$向$v$连一条边权$-w$的边

而且需要满足$dis[i]>=dis[i-1]$

那么$i$向$i-1$连一条边权$0$的边

然后跑最短路,即可

若最后$dis[n]$仍然是$inf$,说明没有限制条件,可以无限远

若有负环存在,会一直在环里减小,其实是无解的

#include 
   
    using namespace std;const int inf = 1e9;const int maxn = 2e6+10;int t,n,q,qq;struct edge{
   	int to,nxt,w;}d[maxn]; int head[maxn],cnt=1;int dis[maxn],vis[maxn],shu[maxn];void add(int u,int v,int w){
   	d[++cnt] = (edge){
   v,head[u],w},head[u] = cnt;}int spfa(int s){
   	for(int i=1;i<=n;i++)	dis[i] = inf, vis[i] = shu[i] = 0;	queue
    
     q; dis[s] = 0; q.push( s );	while( !q.empty() )	{
   		int u = q.front(); q.pop();		vis[u] = 0;		for(int i=head[u];i;i=d[i].nxt )		{
   			int v = d[i].to;			if( dis[v]>dis[u]+d[i].w )			{
   				dis[v] = dis[u]+d[i].w;				if( !vis[v] )				{
   					vis[v] = 1, q.push( v );					if( ++shu[v]==n )	return -1;				}			}		}	}	if( dis[n]==inf )	return -2;	return dis[n];}int main(){
   	cin >> t;	while( t-- )	{
   		cin >> n >> q >> qq;		for(int i=2;i<=n;i++)	add(i,i-1,0);		for(int i=1;i<=q;i++)		{
   			int l,r,w; scanf("%d%d%d",&l,&r,&w);			add(l,r,w);		}		for(int i=1;i<=qq;i++)		{
   			int l,r,w; scanf("%d%d%d",&l,&r,&w);			add(r,l,-w);		}		cout << spfa(1) << endl;		cnt = 1;		for(int i=1;i<=n;i++)	head[i] = 0;	}}
    
   

转载地址：https://issue-is-vegetable.blog.csdn.net/article/details/109985684 如侵犯您的版权，请留言回复原文章的地址，我们会给您删除此文章，给您带来不便请您谅解！