1 #define DeBUG
2 #include <iostream>
3 #include <cstdio>
4 #include <cstring>
5 #include <cmath>
6 #include <cstdlib>
7 #include <algorithm>
8 #include <vector>
9 #include <stack>
10 #include <queue>
11 #include <
string>
12 #include <
set>
13 #include <sstream>
14 #include <map>
15 #include <bitset>
16 #include <windows.h>
17 using namespace std ;
18 #define zero {0}
19 #define INF 2000000000
20 #define EPS 1e-6
21 typedef
long long LL;
22 #define WIDTH 16
23 #define HEIGHT 10
24 const double PI = acos(-
1.0);
25 inline
int sgn(
double x)
26 {
27 return fabs(x) < EPS ?
0 :(x <
0 ? -
1 :
1);
28 }
29 #define n 80
30 int mp[n+
1][n+
1];
31 const short shop_map[
10][
16] =
{
32 {
1,
254,
254,
254,
254,
254,
254,
254,
254,
254,
254,
254,
254,
254,
254,
254
33 },
34 {
2,
3,
4,
5,
0,
6,
75,
7,
8,
73,
9,
10,
0,
11,
254,
254
35 },
36 {
39,
254,
254,
254,
254,
254,
52,
254,
254,
58,
254,
63,
254,
11,
0,
66
37 },
38 {
40,
254,
254,
254,
254,
254,
53,
254,
254,
58,
254,
0,
254,
254,
254,
67
39 },
40 {
41,
12,
13,
14,
77,
15,
0,
16,
17,
74,
18,
19,
20,
76,
21,
67
41 },
42 {
42,
254,
254,
254,
47,
254,
54,
254,
254,
59,
254,
254,
254,
64,
254,
68
43 },
44 {
43,
22,
23,
24,
48,
25,
55,
26,
0,
60,
27,
28,
0,
65,
29,
69
45 },
46 {
44,
254,
254,
254,
49,
254,
56,
254,
254,
61,
254,
254,
254,
254,
254,
70
47 },
48 {
45,
30,
31,
32,
50,
33,
57,
34,
0,
62,
35,
36,
37,
0,
38,
71
49 },
50 {
46,
254,
254,
254,
51,
254,
254,
254,
254,
254,
254,
254,
254,
254,
254,
72
51 }
52 };
53 char road[
100][
100];
54 /**
55 * [Dijkstra description]
56 * @param mp 权值矩阵,从1开始
57 * @param n 点数
58 * @param s 起始点
59 * @param t 终点
60 * @param path 起始点到各点的路(前驱)
61 * @return 起点到终点的最短长度
62 */
63 int Dijkstra(
int s,
int t,
int path[])
64 {
65 int i,j,w,minc;
66 bool visit[n+
1];
67 int price[n+
1];
68 for(i=
1; i<=n; i++
)
69 visit[i]=
false;
70 for(i=
1; i<=n; i++
)
71 {
72 price[i]=
mp[s][i];
73 path[i]=
s;
74 }
75 visit[s]=
true;
76 price[s]=
0;
77 //path[s]=0;
78 for(i=
1; i<n; i++
)
79 {
80 minc=
INF;
81 w=
0;
82 for(j=
1; j<=n; j++
)
83 if((visit[j]==
false)&&(minc>=
price[j]))
84 {
85 minc=
price[j];
86 w=
j;
87 }
88 visit[w]=
true;
89 for(j=
1; j<=n; j++
)
90 if((visit[j]==
false)&&(mp[w][j]!=INF)&&(price[j]>price[w]+
mp[w][j]))
91 {
92 price[j]=price[w]+
mp[w][j];
93 path[j]=
w;
94 }
95 }
96 return price[t];
97 }
98 int dir[
4][
2]= {-
1,
0,
1,
0,
0,-
1,
0,
1};
99 void init()
100 {
101 for(
int i=
1; i<=n; i++
)
102 {
103 for(
int j=
1; j<=n; j++
)
104 {
105 mp[i][j]=
INF;
106 }
107 }
108 memset(road,
0,
sizeof(road));
109 int w;
110 for(
int i=
0; i<
10; i++
)
111 {
112 for(
int j=
0; j<
16; j++
)
113 {
114 for(
int k=
0; k<
4; k++
)
115 {
116 w=
1;
117 int nowx=
i;
118 int nowy=
j;
119 if(shop_map[i][j]==
254)
120 {
121 road[i+
1][j+
1]=
'#';
122 }
123 nowx+=dir[k][
0];
124 nowy+=dir[k][
1];
125 while(shop_map[nowx][nowy]==
0&&nowx>=
0&&nowy>=
0&&nowx<HEIGHT&&nowy<
WIDTH)
126 {
127 w++
;
128 nowx+=dir[k][
0];
129 nowy+=dir[k][
1];
130 }
131 if(nowx<
0||nowy<
0||nowx>=HEIGHT||nowy>=WIDTH||shop_map[nowx][nowy]==
254)
132 continue;
133 int a=
shop_map[i][j];
134 int b=
shop_map[nowx][nowy];
135 if(a>=
1&&a<=n&&b>=
1&&b<=
n)
136 {
137 mp[a][b]=
1;
138 mp[b][a]=
1;
139 }
140 }
141 }
142 }
143 }
144 int main()
145 {
146 #ifdef DeBUGs
147 //freopen("C:\\Users\\Sky\\Desktop\\1.in","r",stdin);
148 freopen(
"C:\\Users\\Sky\\Desktop\\dabiao.txt",
"w",stdout);
149 #endif
150 int m;
151 int path[n+
1];
152 init();
153 int s=
1;
154 int t=
7;
155 int value=
Dijkstra(s,t,path);
156
157
158 //生成地图权值数据
159 // printf("%d\n", n);
160 // printf("{");
161 // for(int i=0;i<n;i++)
162 // {
163 // printf("{" );
164 // printf("%d", mp[i][0]);
165 // for(int j=1;j<n;j++)
166 // {
167 // printf(",%d",mp[i][j]==INF?-1:mp[i][j]);
168 // }
169 // printf("},\n");
170 // }
171 // printf("};");
172
173
174 /测试用
175 for(
int i=
1; i<=n; i++
)
176 {
177 int k=
i;
178 char nowroad[
100][
100];
179 memcpy(nowroad,road,
sizeof(nowroad));
180 nowroad[
1][
1]=
'*';
181 while(k!=
s)
182 {
183 //printf("%d<--",k);
184 for(
int i=
0;i<
10;i++
)
185 for(
int j=
0;j<
16;j++
)
186 {
187 if(shop_map[i][j]==
k)
188 {
189 nowroad[i+
1][j+
1]=
'*';
190 }
191 }
192 k=
path[k];
193 }
194 printf(
"-------------------- %d\n",i);
195 for(
int i=
1;i<=HEIGHT;i++
)
196 {
197 for(
int j=
1;j<=WIDTH;j++
)
198 {
199 printf(
"%c", nowroad[i][j]);
200 }
201 printf(
"\n");
202 }
203 Sleep(
1000);
204 //printf("%d\n",s);
205 }
206 printf(
"%d\n", value);
207 return 0;
208 }
View Code
转载于:https://www.cnblogs.com/Skyxj/p/3464080.html
