#include
<
stdio.h
>
#include
<
stdlib.h
>
#include
<
string
.h
>
#define
N 1005
#define
inf 1<<29
struct
Edge{
int
u, v, d;
Edge(
int
a
=
0
,
int
b
=
0
,
int
c
=
0
):
u(a), v(b), d(c) {}
};
int
n, ml, md, s
=
0
;
Edge ege[
20010
];
int
dist[N];
int
bell_man(){
for
(
int
i
=
1
; i
<=
n;
++
i ) dist[i]
=
inf;
dist[
1
]
=
0
;
int
flag
=
0
;
for
(
int
i
=
1
; i
<=
n;
++
i ){
flag
=
0
;
for
(
int
j
=
0
; j
<
s;
++
j ){
int
u
=
ege[j].u, v
=
ege[j].v, w
=
ege[j].d;
if
( dist[u]
+
w
<
dist[v] ) dist[v]
=
dist[u]
+
w, flag
=
1
;
}
if
(
!
flag )
break
;
}
if
( flag )
return
-
1
;
else
if
( dist[n]
==
inf )
return
-
2
;
else
return
dist[n];
}
int
main(){
scanf(
"
%d%d%d
"
,
&
n,
&
ml,
&
md );
int
u, v, d;
while
( ml
--
){
scanf(
"
%d%d%d
"
,
&
u,
&
v,
&
d );
ege[s
++
]
=
Edge( u, v, d );
}
while
( md
--
){
scanf(
"
%d%d%d
"
,
&
u,
&
v,
&
d );
ege[s
++
]
=
Edge( v, u,
-
d );
}
printf(
"
%d\n
"
, bell_man() );
return
0
;
}
posted on 2009-07-20 19:55
Darren 阅读(496)
评论(0) 编辑 收藏 引用 所属分类:
图论