最短路，建图太麻烦，略过……
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65 |
#include <cstdio> #include <cstring> #include <queue> const
int INF=9999999; using
namespace std; struct
node{ int
v,i; node(int
a,int b){v=a,i=b;} bool
operator <(const
node& a)const{return
v>a.v;} }; int
n,m,map[500][500]; int
done[500],d[500]; int
dij(){ priority_queue q; memset(done,0,sizeof
done); for(int
i=1;i<=(n+1)*(m+1);i++)d[i]=INF; d[1]=0; q.push(node(d[1],1)); while(!q.empty()){ node nd=q.top();q.pop(); int
u=nd.i; if(done[u])continue; done[u]=1; for(int
i=1;i<=(n+1)*(m+1);i++){ if(d[i]>d[u]+map[u][i]){ d[i]=d[u]+map[u][i]; q.push(node(d[i],i)); } } } if(d[(n+1)*(m+1)]==INF)return
-1; else
return d[(n+1)*(m+1)]; } int
main(){ char
s[3];int
v; while(scanf("%d%d",&n,&m),n||m){ for(int
i=1;i<=(n+1)*(m+1);i++)for(int
j=1;j<=(n+1)*(m+1);j++)map[i][j]=INF; int
n1,n2; for(int
i=1;i<=2*n+1;i++){ if(i%2==1){ for(int
j=1;j<=m;j++){ n1=(i/2)*(m+1)+j,n2=n1+1; scanf("%d%s",&v,s); if(v==0)continue; if(s[0]==‘*‘)map[n1][n2]=map[n2][n1]=2520/v; else
if(s[0]==‘<‘)map[n2][n1]=2520/v; else
if(s[0]==‘>‘)map[n1][n2]=2520/v; } }else{ for(int
j=1;j<=m+1;j++){ n1=(i/2-1)*(m+1)+j,n2=n1+m+1; scanf("%d%s",&v,s); if(v==0)continue; if(s[0]==‘*‘)map[n1][n2]=map[n2][n1]=2520/v; else
if(s[0]==‘v‘)map[n1][n2]=2520/v; else
if(s[0]==‘^‘)map[n2][n1]=2520/v; } } } int
r=dij(); if(r==-1)printf("Holiday\n"); else
printf("%d blips\n",r); } return
0; } |
HDU 2722 Here We Go(relians) Again,布布扣,bubuko.com
HDU 2722 Here We Go(relians) Again
原文：http://www.cnblogs.com/forever97/p/3620170.html