SRM 583 Div II Level Three：GameOnABoard，Dijkstra最短路径算法

用Dijkstra实现，之前用Floyd算法写了一个，结果在2s内算不出结果来。

参考了别人算法，学到了set容器的一个用法，用set省去了查找Dijkstra算法中选择最短路径的那一步，set中的第一个元素就是最小值，用priority queue应该也可以。

[cpp]
#include <iostream>
#include <string>
#include <vector>
#include <set>
#include <algorithm>

using namespace std;

#define MAX_SIZE 40
#define INFINITY 100000

#define entry(x, y) make_pair(dd[x][y], make_pair(x, y))

int dijkstra(int x, int y);
vector <string> bcost;

int dd[MAX_SIZE][MAX_SIZE];
int dx[] = {1, -1, 0, 0}, dy[] = {0, 0, 1, -1};
int rows, cols;
class GameOnABoard
{
public:
    int optimalChoice(vector <string> cost);
};

int GameOnABoard::optimalChoice(vector<string> cost)
{
    int rows, cols, minL;
    rows = cost.size();
    cols = cost[0].size();
    minL = INFINITY;
    bcost = cost;
    for (int i = 0; i < rows; i++) {
        for (int j = 0; j < cols; j++) {
            minL = min(minL, dijkstra(i, j));
        }
    }

    return minL;
}

int dijkstra(int x, int y)
{
    int i, j, dir, maxC;
    int cus_x, cus_y, next_x, next_y;
    set < pair<int, pair<int, int>> > s;
    rows = bcost.size();
    cols = bcost[0].size();

    for (i = 0; i < rows; i++) {
        for (j = 0; j < cols; j++) {
            dd[i][j] = INFINITY;
        }
    }
    dd[x][y] = bcost[x][y] - '0';
    s.insert(entry(x, y));

    while (!s.empty()) {
        cus_x = s.begin()->second.first;
        cus_y = s.begin()->second.second;
        s.erase(s.begin());

        for (dir = 0; dir < 4; dir++) {
            next_x = cus_x + dx[dir];
            next_y = cus_y + dy[dir];
            if (next_x < 0 || next_x >= rows || next_y < 0 || next_y >= cols) {
                continue;
            }

            if (dd[next_x][next_y] <= dd[cus_x][cus_y] + bcost[next_x][next_y] - '0') {
                continue;
            }
            s.erase( entry(next_x, next_y) );
            dd[next_x][next_y] = dd[cus_x][cus_y] + bcost[next_x][next_y] - '0';
            s.insert( entry(next_x, next_y) );
        }
    }
    maxC = 0;
    for (i = 0; i < rows; i++) {
        for (j = 0; j < cols; j++) {
            maxC = max(maxC, dd[i][j]);
        }
    }
    return maxC;
}

补充：软件开发 , C++ ,