POJ 3169 Layout

两个关系好的牛之间不能超过一定的距离，两个关系不好的牛之间的距离不能少一定的距离。如果存在负还输出-1，牛1和牛N不连通输出-2，否则输出他们的之间距离。

 1 #include<cstdio>
 2 #include<cstring>
 3 #include<cstdlib>
 4 
 5 struct N
 6 {
 7     int u,v,w;
 8 } edge[20010];
 9 
10 int dis[1010];
11 int INF = (1<<29);
12 
13 int bellman_ford(int n,int e)
14 {
15     int flag;
16     int i,j,k,u,v,w;
17     for(i = 1;i < n; i++)
18     {
19         flag = 1;
20         for(j = 0;j < e; j++)
21         {
22             u = edge[j].u;
23             v = edge[j].v;
24             w = edge[j].w;
25             if(dis[u] + w < dis[v])
26             {
27                 dis[v] = dis[u] + w;
28                 flag = 0;
29             }
30         }
31         if(flag) break;
32     }
33     for(j = 0;j < e; j++)
34     {
35          u = edge[j].u;
36             v = edge[j].v;
37             w = edge[j].w;
38             if( dis[u] + w < dis[v])
39             {
40                 return 1;
41             }
42     }
43     return 0;
44 }
45 
46 int main()
47 {
48     int n,m,l,i,e,u,v,w;
49    scanf("%d %d %d",&n,&m,&l);
50     
51         for(i = 1; i <= n; i++)
52         {
53             dis[i] = INF;
54         }
55         dis[1] = 0;
56         for(e = 0, i = 0; i < m; i++)
57         {
58             scanf("%d %d %d",&u,&v,&w);
59             edge[e].u = u;
60             edge[e].v = v;
61             edge[e].w = w;
62             e++;
63         }
64         for(i = 0; i < l; i++)
65         {
66             scanf("%d %d %d",&u,&v,&w);
67             edge[e].u = v;
68             edge[e].v = u;
69             edge[e].w = -w;
70             e++;
71         }
72 
73    
74 
75         if(bellman_ford(n,e))
76             printf("-1\n");
77         else
78         {
79             if(dis[n] == INF)
80                 printf("-2\n");
81             else printf("%d\n",dis[n]);
82         }
83     
84     
85     return 0;
86 }