/*
因为求的是最大距离,所以用最短路,要找出形如x[i]<=x[j]+c的不等式
①序号大的牛不可能在序号小的牛的前面 -> x[i]<=x[i+1]; i+1->i , 0
②好感度 -> x[b]-x[a]<=c -> x[b]<=x[a]+c; a->b , c
③反感度 -> x[b]-x[a]>=c -> x[a]<=x[b]-c. b->a , -c
还需要找一个超级源点(记超级源点为x[0]),发现这里求的距离都是牛之间的相对距离,所以联想到令x[0]=0,
又因为求的是形如x[i]<=x[j]+c的不等式,所以将所有点放在0点的左侧就可以得出 x[i]<=x[0]+0的不等式,这样从源点出发可以遍历所有的点,
那么就可以遍历到所有的边。
所以就需要从源点向所有点连一条长度是0的边,(PS:这里可以通过在建立队列的时候将所有的点推入队列来代替)
当存在负环时,不存在方案输出-1,
因为求的是一个相对距离,所以记第i头牛到第1头牛的距离为dist[i],那么第1头牛到第N头牛之间的距离就是dist[N],当dist[N]=INF时输出-2.
*/
#include <iostream>
#include <cstring>
#include <queue>
using namespace std;
const int N = 1010 , M = 21010 , INF = 0x3f3f3f3f;
int e[M] , ne[M] , w[M] , h[N] , idx;
bool st[N];
int cnt[N];
int dist[N];
int n , m1 , m2;
void add(int a , int b , int c)
{
e[idx] = b , ne[idx] = h[a] , w[idx] = c , h[a] = idx++;
}
bool spfa(int size)
{
memset(dist , 0x3f , sizeof dist);
memset(st , 0 , sizeof st);
memset(cnt , 0 , sizeof cnt);
queue<int> q;
for(int i = 1 ; i <= size ; i++)
{
q.push(i);
dist[i] = 0;
st[i] = true;
}
while(q.size())
{
int t = q.front();
st[t] = false;
q.pop();
for(int i = h[t] ; ~i ; i = ne[i])
{
int j = e[i];
if(dist[j] > dist[t] + w[i])
{
dist[j] = dist[t] + w[i];
cnt[j] = cnt[t] + 1;
if(cnt[j] >= n) return false;
if(!st[j])
{
q.push(j);
st[j] = true;
}
}
}
}
return true;
}
int main()
{
cin >> n >> m1 >> m2;
memset(h , -1 , sizeof h);
for(int i = 1 ; i < n ; i++) add(i + 1 , i , 0);
while(m1--)
{
int a , b , c;
cin >> a >> b >> c;
if(a > b) swap(a , b);
add(a , b , c);
}
while(m2--)
{
int a , b , c;
cin >> a >> b >> c;
if(a > b) swap(a , b);
add(b , a , -c);
}
if(!spfa(n)) cout << -1 << endl;//第一问判断是否有负环,所以把所有点推入
else
{
spfa(1);//第二问求dist[n],所以只用推如第一个点
if(dist[n] == INF) cout << -2 << endl;
else cout << dist[n] << endl;
}
return 0;
}
第四行反感度那里是应该是笔误了,应该将
c
改成-c
👌
建立超级原点是为了判断是否有负环,这样可以以所有点为起点跑一遍spfa,如果不建立超级远点那就得跑n次spfa()
从1出发不一定可以遍历所有边,所以1不可以
感觉可以,因为a[i]<=a[n]+0,这样就是把dist[n]记为0,然后去求dist[1]
你可以试试,我这题是去年做的,有点久了
n才是。因为建立应该是从2向1从3向2 n 向n-1所以n可以去任何点
建立了超级原点本质也是跑n次spfa啊