题解 | #刺客信条#

dijkstra做法

#include <cstring>
#include <iostream>
#include <algorithm>
#include <queue>

#define x first
#define y second

using namespace std;

typedef pair<int, int> PII;

const int E = 40, N = 1000, M = N * 4;

int n, m, S, T;
int h[N], e[M], ne[M], w[M], idx;
char g[E][E];
bool st[N];
int dist[N];
int dx[4] = {-1, 0, 1, 0}, dy[4] = {0, 1, 0, -1};

int get(int x, int y)
{
    return x * m + y;
}

int get_w(char c)
{
    if (c == 'A' || c == 'B' || c == 'C') return 100;
    if (c == 'S' || c == 'E') return 0;
    return c - '0';
}

void add(int a, int b, int c)
{
    e[idx] = b, w[idx] = c, ne[idx] = h[a], h[a] = idx ++ ;
}

void bulid()
{
    memset(h, -1, sizeof h);
    
    for (int i = 0; i < n; i ++ )
        for (int j = 0; j < m; j ++ )
        {
            for (int u = 0; u < 4; u ++ )
            {
                int a = i + dx[u], b = j + dy[u];
                if (a < 0 || a >= n || b < 0 || b >= m) continue;
                add(get(i, j), get(a, b), get_w(g[a][b]));
            }
        }
}

int dijkstra()
{
    memset (dist, 0x3f, sizeof dist);
    dist[S] = 0;

    priority_queue<PII, vector<PII>, greater<PII>> heap;
    heap.push({0, S});

    while (heap.size())
    {
        auto t = heap.top();
        heap.pop();

        int ver = t.second, distance = t.first;

        if (st[ver]) continue;
        st[ver] = true;
        
        for (int i = h[ver]; ~i; i = ne[i] )
        {
            int j = e[i];
            if (dist[j] > distance + w[i])
            {
                dist[j] = distance + w[i];
                heap.push({dist[j], j});
            }
        }
    }

    return dist[T];
}

int main()
{
    cin >> n >> m;
    for (int i = 0; i < n; i ++ )
        for (int j = 0; j < m; j ++ )
        {
            cin >> g[i][j];
            if (g[i][j] == 'S') S = get(i, j);
            if (g[i][j] == 'E') T = get(i, j);
        }

    bulid();

    cout << spfa() << endl; 
    
    return 0;
}

spfa做法

#include <cstring>
#include <iostream>
#include <algorithm>
#include <queue>

#define x first
#define y second

using namespace std;

typedef pair<int, int> PII;

const int E = 40, N = 1000, M = N * 4;

int n, m, S, T;
int h[N], e[M], ne[M], w[M], idx;
char g[E][E];
bool st[N];
int dist[N], q[N];
int dx[4] = {-1, 0, 1, 0}, dy[4] = {0, 1, 0, -1};

int get(int x, int y)
{
    return x * m + y;
}

int get_w(char c)
{
    if (c == 'A' || c == 'B' || c == 'C') return 100;
    if (c == 'S' || c == 'E') return 0;
    return c - '0';
}

void add(int a, int b, int c)
{
    e[idx] = b, w[idx] = c, ne[idx] = h[a], h[a] = idx ++ ;
}

void bulid()
{
    memset(h, -1, sizeof h);
    
    for (int i = 0; i < n; i ++ )
        for (int j = 0; j < m; j ++ )
        {
            for (int u = 0; u < 4; u ++ )
            {
                int a = i + dx[u], b = j + dy[u];
                if (a < 0 || a >= n || b < 0 || b >= m) continue;
                add(get(i, j), get(a, b), get_w(g[a][b]));
            }
        }
}

int spfa()
{
    memset(dist, 0x3f, sizeof dist);
    dist[S] = 0;

    int hh = 0, tt = 1;
    q[0] = S;
    st[S] = true;
    
    while (hh != tt)
    {
        int t = q[hh ++ ];
        if (hh == N) hh = 0;
        st[t] = false;
        
        for (int i = h[t]; ~i; i = ne[i])
        {
            int j = e[i];
            if (dist[j] > dist[t] + w[i])
            {
                dist[j] = dist[t] + w[i];
                if (!st[j])
                {
                    q[tt ++ ] = j;
                    if (tt == N) tt = 0;
                    st[j] = true;
                }
            }
        }
    }
    
    return dist[T];
}

int main()
{
    cin >> n >> m;
    for (int i = 0; i < n; i ++ )
        for (int j = 0; j < m; j ++ )
        {
            cin >> g[i][j];
            if (g[i][j] == 'S') S = get(i, j);
            if (g[i][j] == 'E') T = get(i, j);
        }

    bulid();

    cout << spfa() << endl; 
    
    return 0;
}