Wormholes--POJ 3259
11898 ワード
1、テーマタイプ:図論、最短経路、Bellman-Fordアルゴリズム.
2、問題を解く構想:(1)入力によってすべての辺を記録し、そのうち無方向の辺が有方向の辺記録に変換する.(2)Bellman‐Fordアルゴリズムはすべての辺を緩和し,負の輪が存在するかどうかを探る.
3、注意事項:Mov[]配列の大きさに注意する.
4、実現方法:
2、問題を解く構想:(1)入力によってすべての辺を記録し、そのうち無方向の辺が有方向の辺記録に変換する.(2)Bellman‐Fordアルゴリズムはすべての辺を緩和し,負の輪が存在するかどうかを探る.
3、注意事項:Mov[]配列の大きさに注意する.
4、実現方法:
#include
<
iostream
>
using
namespace
std;
#define
Maxn 510
#define
Maxw 6000
#define
INF 99999
struct
TMove{
int
s,e,t;
};
TMove Mov[Maxw];
int
n,m,w,flag,cnt;
void
Bellman_ford()
{
int
i,j,start,end,time;
double
d[Maxn];
for
(i
=
0
;i
<
n;i
++
)
d[i]
=
INF;
d[
0
]
=
0
;
for
(i
=
1
;i
<
n;i
++
)
{
for
(j
=
0
;j
<
cnt;j
++
)
{
start
=
Mov[j].s;
end
=
Mov[j].e;
time
=
Mov[j].t;
if
(d[end]
>
d[start]
+
time)
d[end]
=
d[start]
+
time;
}
}
for
(j
=
0
;j
<
cnt;j
++
)
{
start
=
Mov[j].s;
end
=
Mov[j].e;
time
=
Mov[j].t;
if
(d[end]
>
d[start]
+
time)
{
flag
=
1
;
return
;
}
}
}
int
main()
{
int
i,f,s,e,t;
cin
>>
f;
while
(f
--
)
{
cin
>>
n
>>
m
>>
w;
memset(Mov,
0
,
sizeof
(Mov));
flag
=
0
,cnt
=
0
;
for
(i
=
0
;i
<
m;i
++
)
{
cin
>>
s
>>
e
>>
t;
s
--
,e
--
;
Mov[cnt].s
=
s;
Mov[cnt].e
=
e;
Mov[cnt].t
=
t;
cnt
++
;
Mov[cnt].s
=
e;
Mov[cnt].e
=
s;
Mov[cnt].t
=
t;
cnt
++
;
}
for
(i
=
0
;i
<
w;i
++
)
{
cin
>>
s
>>
e
>>
t;
s
--
,e
--
;
Mov[cnt].s
=
s;
Mov[cnt].e
=
e;
Mov[cnt].t
=-
t;
cnt
++
;
}
Bellman_ford();
if
(flag)
cout
<<
"
YES
"
<<
endl;
else
cout
<<
"
NO
"
<<
endl;
}
return
1
;
}