萌新0分求助

Q：为什么要用Dijkstra做？而不是bfs？

A：闲的（

以上结尾废话↑

实在不行我换成bfs做

记录

思路：在地图中如果遇到0，就向上和向左建边，如果那两个点也是0。然后做dij。

把二维的坐标转换成一维的坐标没什么问题，就是建边时有点问题，应该是有向图，求调QAQ

#include<bits/stdc++.h>
#define int long long
using namespace std;
const int N=1e5+5;
const int INF=1e9;
int n,m,s,t,cnt; 
struct Edge{
    int v,w;
    Edge(int v,int w):v(v),w(w){}
};
struct Node{
    int u,d;
    Node(int u,int d):u(u),d(d){}
    bool operator < (const Node &a) const{
        return d>a.d;
    }
};
int d[N],vis[N];
char a[1005][1005];
vector<Edge> adj[N];
void dij(){
    for(int i=1;i<=n;i++)d[i]=INF;
    d[s]=0;
    priority_queue<Node>q;
    q.push(Node(s,0));
    while(!q.empty()){
        int u=q.top().u;
        q.pop();
        if(u==t)return;
        if(vis[u])continue;
        vis[u]=1;
        for(int i=0;i<adj[u].size();i++){
            int v=adj[u][i].v;
            int w=adj[u][i].w;
            if(d[v]>d[u]+w){
                d[v]=d[u]+w;
                q.push(Node(v,d[v]));
            }
        }
    }
}
signed main(){
    cin>>n;
    for(int i=1;i<=n;i++){
        for(int j=1;j<=n;j++){
            cin>>a[i][j];
            int u=(i-1)*n+j,v,w=1;
            if(i==1)continue; 
            if(a[i][j]=='1')continue;
            if(a[i-1][j]=='0'){
                v=(i-2)*n+j;
                adj[u].push_back(Edge(v,w));
                adj[v].push_back(Edge(u,w));
            }
            if(a[i][j-1]=='0'){
                v=(i-1)*n+(j-1);
                adj[u].push_back(Edge(v,w));
                adj[v].push_back(Edge(u,w));
            }
        }
    }
    int s1,s2,t1,t2;
    cin>>s1>>s2>>t1>>t2;
    s=(s1-1)*n+s2,t=(t1-1)*n+t2;
    dij();
    cout<<d[t];
    return 0;
}