C++ 最短路徑問題 Dijkstra應用

題目連結：Sprout Online Judge No. 393

這題用 Bellman-Ford 必定 TLE

#include<bits/stdc++.h>
using namespace std;
#define INF 0x3f3f3f3f
const int dr[4]{1,0,-1,0},dc[4]{0,1,0,-1};

int dt[2005][2005];
string mp[2005];
bitset<2005> v[2005];

struct position{
    int r,c;
    bool operator==(position a){
        return r==a.r && c==a.c;
    }
};
bool operator<(position a,position b){
    return dt[a.r][a.c]>dt[b.r][b.c];
}

int main(){
    ios::sync_with_stdio(0);cin.tie(0);

    int n,m,ans=INF;
    cin>>n>>m;

    for(int i=0;i<n;i++) for(int j=0;j<m;j++) dt[i][j]=INF;

    for(int i=0;i<n;i++){
        cin>>mp[i];
    }

    position ps,pe;
    cin>>ps.r>>ps.c;ps.r--;ps.c--;
    cin>>pe.r>>pe.c;pe.r--;pe.c--;
    dt[ps.r][ps.c]=0;

    priority_queue<position> bfs;
    bfs.push(ps);

    int ct;
    position now,next,mnPos;
    while(!bfs.empty()){
        now=bfs.top();
        bfs.pop();
        v[now.r][now.c]=1;
        for(int i=0;i<4;i++){
            next.r=now.r+dr[i];
            next.c=now.c+dc[i];
            if(next.r>=0 && next.c>=0 && next.r<n && next.c<m){
                ct=dt[now.r][now.c];
                if(mp[next.r][next.c]=='.')
                    ct++;
                if(pe==next)
                    ans=min(ans,ct);
                if(!v[next.r][next.c]){
                    v[next.r][next.c]=1;
                    dt[next.r][next.c]=ct;
                    bfs.push(next);
                }
            }
        }
    }
    cout<<ans<<"\n";
    return 0;
}