#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 閱讀(516)
評論(0) 編輯 收藏 引用 所屬分類:
圖論