4416 FFF 团卧底的后宫
时间限制: 1 s
空间限制: 128000 KB
题目等级 : 黄金 Gold
题目描述 Description
你在某日收到了 FFF 团卧底的求助,在他某日旅游回来,他的后宫们出现了一些不可调和的矛盾,如果 FFF 团卧底把自己的宝贝分给 a 号妹子,那么 b 号妹子至少要在站在 a 号妹子的右边距离 d,妹子才愿意得到那个宝贝。可是后宫里也有玩得好的妹子呀,她们总是渴望亲近一点,如果把自己的宝贝分给 a 号妹子,那么与她亲近的妹子与 a 号妹子的距离不会超过 l。现在总共有 n 个妹子,k 个这样的矛盾关系,m 个亲近关系。假设他的宝贝是无限的,保证每一个妹子都有宝贝的情况下,第 n 个妹子和第一个妹子的最远距离是多少呢?
输入描述 Input Description
第一行为 n,m,k
此后 m 行为亲近关系
此后 k 行为矛盾关系
输出描述 Output Description
一行,为最长的距离
样例输入 Sample Input
4 2 1
1 3 100
2 4 200
2 3 33
样例输出 Sample Output
267
数据范围及提示 Data Size & Hint
对于 40%的数据,n<=100
对于 100%的数据,n<=1000,m<=10000,从 1 开始编号,距离在 int 范围内
代码：
#include<cstdio>
#define INF 0x7fffffff
#define maxn 10000
#include<iostream> using namespace std; int n,ml,md,cnt=; struct cf
{
int to[maxn],a[maxn],next[maxn],head[maxn],w[maxn],q[maxn*],tt[maxn];
long long dis[maxn];
bool vis[maxn];
int insert(int u,int v,int ww)
{
to[++cnt]=v; next[cnt]=head[u]; head[u]=cnt; w[cnt]=ww;
}
cf()
{
scanf("%d%d%d",&n,&ml,&md);
for (int i=;i<=ml;i++)
{
int u,v,w;
scanf("%d%d%d",&u,&v,&w);
insert(u,v,w);
}
for (int i=;i<=md;i++)
{
int u,v,w;
scanf("%d%d%d",&u,&v,&w);
insert(v,u,-w);
}
for (int i=;i<=n;i++) dis[i]=0x7fffffff;
}
int spfa()
{
int h=,t=;
q[]=;
vis[]=;
tt[]++;
dis[]=;
while (t<h)
{
int now=q[t++];
for (int i=head[now];i;i=next[i])
{ if (dis[to[i]]>dis[now]+w[i])
{
tt[to[i]]++;
if (tt[to[i]]==n+) return ;
dis[to[i]]=dis[now]+w[i];
if (!vis[to[i]])
{
vis[to[i]]=;
q[h++]=to[i];
}
}
}
vis[now]=;
}
return ;
}
void print()
{
if(!spfa()) printf("-1");
else if(dis[n]==0x7fffffff) printf("-2");
else printf("%lld\n",dis[n]);
} }cf;
int main()
{
cf.print();
return ;
}