Dijkstra

gistfile1.txt

108
109
110
111
int N, M;
int maze [MAX_N] [MAX_M];
int dis [MAX_N][MAX_M];
112
int dijkstra(int sx, int sy, int tx, int ty)
1130 {
114
115
priority_queue<T, vector<T›, greater<T›> pas
116
117
memset (dis, INF8, sizeof (dis)) ;
118
119
120€
pq. emplace(maze [sx][sy], sx, sy) ;
while (Ipq.empty () )
{
121
int d, ux, uy;
122
123
124
tie(d, ux, uy) = pq. top () , pq. pop () ;
125
if (dis [ux][uy] I= INF32) continue;
126
127
128
129 E
dis [ux][uy] = d;
REP (i, 4)
{
130
131
int vx = ux + dx[i];
int vy = uy + dy[i];
132
133
134
if (vx < 0 || N <= vX || vy < © || M <= vy || dis [vx][vy] != INF32)
continue;
135
136
137
138
pq. emplace (d + maze [vx][vy], vx, vy) ;
}//REP
}//while
139
140
return dis [tx][ty];
141
_ }//dijkstra