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; 
}