首页 > 3.12阿里笔试问题一
头像
ChenJianhui
编辑于 2021-03-23 08:03
+ 关注

3.12阿里笔试问题一

3.12笔试问题一
根据数据构建图,利用深搜+回溯求出由出发点x至目的地y的最短距离。若不存在路径则返回-1,存在则返回最小距离。
打卡一篇小笔记,有不足之处还希望各位提出。

#include<bits/stdc++.h> 
using namespace std;

void dfs(vector<vector<int>>& G,vector<bool>& visited,int y,int& cur,int& index,int& res)
{
    if(index == y){
        res = min(res,cur);
        return;
    }
    if(visited[index])    return;
    visited[index] = true;
    for(int i = 1;i < G[index].size();i++)
    {
        if(!visited[i] && G[index][i] == 1){
            cur++;
            dfs(G,visited,y,cur,i,res);
            cur--;
        }
    }
    return;
}

int main()
{
    int n,m;
    cin>>n>>m;
    int q;
    vector<vector<int>> G(n+1,vector<int>(n+1));
    while(m--)
    {
        int x,y;
        cin>>x>>y;
        G[x][y] = 1;
    }

    for(int i = 1;i < n+1;i++)
    {
        for(int j = 1;j < n+1;j++)
        {
            cout<<G[i][j];
        }
        cout<<endl;
    }

    cin>>q;
    while(q--)
    {
        int x,y;
        cin>>x>>y;
        int res = 65535;
        int cur= 0;
        int i;
        vector<bool> visited(n+1,false);
        for(i = 1; i < n+1 ;i++){
            if(i == y && G[x][y] == 1){
                res = 1;
                break;
            }
            if(!visited[i] && G[x][i] == 1)
            {    
                cur = 1;
                dfs(G,visited,y,cur,i,res);
            }
        }
        if(i == n+1 && res == 65535)    cout<<-1<<endl;
        else cout<<res<<endl;
    }
    return 0;
}

全部评论

(1) 回帖
加载中...
话题 回帖

推荐话题

相关热帖

历年真题 真题热练榜 24小时
技术(软件)/信息技术类
查看全部

近期精华帖

热门推荐