#include
<
stdio.h
>
#include
<
limits.h
>
#include
<
stdlib.h
>
#include
<
math.h
>
#include
<
string
.h
>
#define
N 110
int
graph[N][N];
int
rank[N];
int
value[N];
int
m, n, len;
![](/Images/OutliningIndicators/None.gif)
bool
findrank(
int
t )
![](/Images/OutliningIndicators/ExpandedBlockStart.gif)
{
for
(
int
i
=
0
; i
<
t;
++
i )
if
( value[i]
==
t )
return
true
;
return
false
;
}
int
dis(
int
Rank )
![](/Images/OutliningIndicators/ExpandedBlockStart.gif)
{
bool
visite[N];
int
result[N];
rank[
0
]
=
Rank;
for
(
int
i
=
1
; i
<=
n;
++
i )
![](/Images/OutliningIndicators/ExpandedSubBlockStart.gif)
{
int
t
=
Rank
-
rank[i];
![](/Images/OutliningIndicators/ExpandedSubBlockStart.gif)
if
( t
<=
m
&&
t
>=
0
)
{ visite[i]
=
false
; result[i]
=
graph[
0
][i]; }
else
{ visite[i]
=
true
; result[i]
=
-
1
; }
}
visite[
0
]
=
true
;
for
(
int
t
=
1
; t
<=
n;
++
t )
![](/Images/OutliningIndicators/ExpandedSubBlockStart.gif)
{
int
min
=
INT_MAX;
int
k
=
-
1
;
for
(
int
i
=
0
; i
<=
n;
++
i )
if
(
!
visite[i]
&&
result[i]
>=
0
&&
result[i]
<
min )
![](/Images/OutliningIndicators/ExpandedSubBlockStart.gif)
{
min
=
result[i];
k
=
i;
}
if
( k
==
-
1
)
break
;
visite[k]
=
true
;
for
(
int
i
=
1
; i
<=
n;
++
i )
![](/Images/OutliningIndicators/ExpandedSubBlockStart.gif)
{
if
(
!
visite[i]
&&
graph[k][i]
>=
0
&&
result[k]
>=
0
&&
( result[k]
+
graph[k][i]
<
result[i]
||
result[i]
==
-
1
) )
result[i]
=
result[k]
+
graph[k][i];
}
}
return
result[
1
];
}
int
main()
![](/Images/OutliningIndicators/ExpandedBlockStart.gif)
{
scanf(
"
%d%d
"
,
&
m,
&
n);
len
=
0
;
memset( graph,
-
1
,
sizeof
(
int
)
*
N
*
N );
for
(
int
i
=
1
; i
<=
n;
++
i )
![](/Images/OutliningIndicators/ExpandedSubBlockStart.gif)
{
int
va, ra, nn;
scanf(
"
%d%d%d
"
,
&
va,
&
ra,
&
nn );
graph[
0
][i]
=
va;
rank[i]
=
ra;
if
(
!
findrank( ra ) ) value[len
++
]
=
ra;
for
(
int
j
=
0
; j
<
nn;
++
j )
![](/Images/OutliningIndicators/ExpandedSubBlockStart.gif)
{
int
a, b;
scanf(
"
%d%d
"
,
&
a,
&
b);
graph[a][i]
=
b;
}
}
int
min
=
INT_MAX;
for
(
int
i
=
0
; i
<
len;
++
i )
![](/Images/OutliningIndicators/ExpandedSubBlockStart.gif)
{
int
t
=
dis( value[i] );
if
( t
<
min
&&
t
!=
-
1
) min
=
t;
}
printf(
"
%d\n
"
, min );
return
0
;
}
posted on 2008-10-29 21:01
Darren 阅读(317)
评论(0) 编辑 收藏 引用 所属分类:
图论