POJ 3653 Here We Go(relians)Again(最短)
58187 ワード
标题:与えられた(n+1)*(m+1)個の点で、構成された有向図では、各辺の値が限界速度であり、各段の辺の長さがLENであり、起点から終点までの最短距離を求める.
考え方:テクニックはありません.最短アルゴリズムです.2次元の点hashを1次元にすればいいです.n*k+mを入力するときは、データ量が少ないので、O(n^2)のdijでいいです.16 msでpriority_を使います.queue最適化で0 msできます.
O(nlgn):
O(n^2):
考え方:テクニックはありません.最短アルゴリズムです.2次元の点hashを1次元にすればいいです.n*k+mを入力するときは、データ量が少ないので、O(n^2)のdijでいいです.16 msでpriority_を使います.queue最適化で0 msできます.
O(nlgn):
#include
<
iostream
>
#include
<
cstdio
>
#include
<
algorithm
>
#include
<
memory.h
>
#include
<
cmath
>
#include
<
bitset
>
#include
<
queue
>
#include
<
vector
>
using
namespace
std;
const
int
BORDER
=
(
1
<<
20
)
-
1
;
const
int
MAXSIZE
=
37
;
const
int
MAXN
=
1105
;
const
int
INF
=
1000000000
;
#define
CLR(x,y) memset(x,y,sizeof(x))
#define
ADD(x) x=((x+1)&BORDER)
#define
IN(x) scanf("%d",&x)
#define
OUT(x) printf("%d
",x)
#define
MIN(m,v) (m)<(v)?(m):(v)
#define
MAX(m,v) (m)>(v)?(m):(v)
#define
ABS(x) ((x)>0?(x):-(x))
#define
LEN 2520
#define
SET_NODE(no,a,b) {no.u=a;no.val=b;}
typedef
struct
{
int
v,next;
int
val;
}Edge;
typedef
struct
{
int
u;
int
val;
}Node;
bool
operator
<
(
const
Node
&
a,
const
Node
&
b)
{
return
a.val
>
b.val;
}
Edge edge[MAXN
*
MAXN];
int
n,m,start,end,index;
int
dist[MAXN],net[MAXN];
bool
visit[MAXN];
void
add_edge(
const
int
&
u,
const
int
&
v,
const
int
&
sp)
{
edge[index].v
=
v;
edge[index].next
=
net[u];
edge[index].val
=
sp;
net[u]
=
index
++
;
}
void
add_input(
const
int
&
u,
const
int
&
v,
const
int
&
sp,
const
char
&
c)
{
if
(c
==
'
*
'
)
{
add_edge(u,v,sp);
add_edge(v,u,sp);
return
;
}
if
( c
==
'
>
'
||
c
==
'
v
'
)
add_edge(u,v,sp);
else
add_edge(v,u,sp);
}
int
init()
{
index
=
0
;
CLR(net,
-
1
);
CLR(visit,
0
);
CLR(dist,
127
);
return
0
;
}
int
input()
{
int
i,j,u,v,tmp,sp;
char
ch;
for
(i
=
0
; i
<
n
-
1
;
++
i)
{
for
(j
=
0
; j
<
m
-
1
;
++
j)
{
scanf(
"
%d %c
"
,
&
sp,
&
ch);
if
(sp
==
0
)
continue
;
u
=
i
*
m
+
j;
v
=
u
+
1
;
add_input(u,v,sp,ch);
}
for
(j
=
0
; j
<
m;
++
j)
{
scanf(
"
%d %c
"
,
&
sp,
&
ch);
if
(sp
==
0
)
continue
;
u
=
i
*
m
+
j;
v
=
(i
+
1
)
*
m
+
j;
add_input(u,v,sp,ch);
}
}
for
(j
=
0
; j
<
m
-
1
;
++
j)
{
scanf(
"
%d %c
"
,
&
sp,
&
ch);
u
=
(n
-
1
)
*
m
+
j;
v
=
u
+
1
;
if
(sp
==
0
)
continue
;
add_input(u,v,sp,ch);
}
return
0
;
}
int
dij()
{
int
i,j,u,tmp,mark,mmin,v;
int
N
=
n
*
m;
priority_queue
<
Node
>
que;
Node node,t_node;
while
(
!
que.empty())
que.pop();
SET_NODE(t_node,
0
,
0
);
que.push(t_node);
dist[
0
]
=
0
;
CLR(visit,
0
);
while
(
!
que.empty())
{
node
=
que.top();
que.pop();
u
=
node.u;
if
(visit[node.u])
continue
;
if
(u
==
N
-
1
)
return
node.val;
visit[u]
=
true
;
for
(i
=
net[u]; i
!=
-
1
; i
=
edge[i].next)
{
v
=
edge[i].v;
if
(visit[v])
continue
;
tmp
=
dist[u]
+
LEN
/
edge[i].val;
if
(dist[v]
>
tmp)
{
dist[v]
=
tmp;
SET_NODE(t_node,v,tmp);
que.push(t_node);
}
}
}
return
-
1
;
}
int
work()
{
int
i,j,ans;
ans
=
dij();
if
(ans
==
-
1
)
printf(
"
Holiday
"
);
else
printf(
"
%d blips
"
,ans);
return
0
;
}
int
main()
{
while
(scanf(
"
%d%d
"
,
&
n,
&
m))
{
if
(
!
n
&&
!
m)
break
;
++
n,
++
m;
init();
input();
work();
}
return
0
;
}
O(n^2):
#include
<
iostream
>
#include
<
cstdio
>
#include
<
algorithm
>
#include
<
memory.h
>
#include
<
cmath
>
#include
<
bitset
>
#include
<
queue
>
#include
<
vector
>
using
namespace
std;
const
int
BORDER
=
(
1
<<
20
)
-
1
;
const
int
MAXSIZE
=
37
;
const
int
MAXN
=
1105
;
const
int
INF
=
1000000000
;
#define
CLR(x,y) memset(x,y,sizeof(x))
#define
ADD(x) x=((x+1)&BORDER)
#define
IN(x) scanf("%d",&x)
#define
OUT(x) printf("%d
",x)
#define
MIN(m,v) (m)<(v)?(m):(v)
#define
MAX(m,v) (m)>(v)?(m):(v)
#define
ABS(x) ((x)>0?(x):-(x))
#define
LEN 2520
typedef
struct
{
int
v,next;
int
val;
}Edge;
typedef
struct
{
int
u;
int
val;
}Node;
bool
operator
<
(
const
Node
&
a,
const
Node
&
b)
{
return
a.val
>
b.val;
}
Edge edge[MAXN
*
MAXN];
int
n,m,start,end,index;
int
dist[MAXN],net[MAXN];
bool
visit[MAXN];
void
add_edge(
const
int
&
u,
const
int
&
v,
const
int
&
sp)
{
edge[index].v
=
v;
edge[index].next
=
net[u];
edge[index].val
=
sp;
net[u]
=
index
++
;
}
void
add_input(
const
int
&
u,
const
int
&
v,
const
int
&
sp,
const
char
&
c)
{
if
(c
==
'
*
'
)
{
add_edge(u,v,sp);
add_edge(v,u,sp);
return
;
}
if
( c
==
'
>
'
||
c
==
'
v
'
)
add_edge(u,v,sp);
else
add_edge(v,u,sp);
}
int
init()
{
index
=
0
;
CLR(net,
-
1
);
CLR(visit,
0
);
CLR(dist,
127
);
return
0
;
}
int
input()
{
int
i,j,u,v,tmp,sp;
char
ch;
for
(i
=
0
; i
<
n
-
1
;
++
i)
{
for
(j
=
0
; j
<
m
-
1
;
++
j)
{
//
cin>>sp>>ch;
scanf(
"
%d %c
"
,
&
sp,
&
ch);
if
(sp
==
0
)
continue
;
u
=
i
*
m
+
j;
v
=
u
+
1
;
add_input(u,v,sp,ch);
}
for
(j
=
0
; j
<
m;
++
j)
{
//
cin>>sp>>ch;
scanf(
"
%d %c
"
,
&
sp,
&
ch);
if
(sp
==
0
)
continue
;
u
=
i
*
m
+
j;
v
=
(i
+
1
)
*
m
+
j;
add_input(u,v,sp,ch);
}
}
for
(j
=
0
; j
<
m
-
1
;
++
j)
{
//
cin>>sp>>ch;
scanf(
"
%d %c
"
,
&
sp,
&
ch);
u
=
(n
-
1
)
*
m
+
j;
v
=
u
+
1
;
if
(sp
==
0
)
continue
;
add_input(u,v,sp,ch);
}
return
0
;
}
int
dij()
{
int
i,j,tmp,mark,mmin,v;
int
N
=
n
*
m;
dist[
0
]
=
0
;
CLR(visit,
0
);
for
(i
=
0
; i
<
N;
++
i)
{
mmin
=
INF;
for
(j
=
0
; j
<
N;
++
j)
if
(
!
visit[j]
&&
mmin
>
dist[j])
{
mmin
=
dist[j];
mark
=
j;
}
visit[mark]
=
true
;
for
(j
=
net[mark]; j
!=
-
1
; j
=
edge[j].next)
{
tmp
=
LEN
/
edge[j].val;
v
=
edge[j].v;
if
(
!
visit[v]
&&
dist[v]
>
tmp
+
mmin)
{
dist[v]
=
tmp
+
mmin;
}
}
}
if
(dist[N
-
1
]
>
INF)
return
-
1
;
return
dist[N
-
1
];
}
int
work()
{
int
i,j,ans;
ans
=
dij();
if
(ans
==
-
1
)
printf(
"
Holiday
"
);
else
printf(
"
%d blips
"
,ans);
return
0
;
}
int
main()
{
while
(scanf(
"
%d%d
"
,
&
n,
&
m))
{
if
(
!
n
&&
!
m)
break
;
++
n,
++
m;
init();
input();
work();
}
return
0
;
}