C++之路进阶——codevs4416（FFF的后宫）

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 ;
      }