LeetCode 815 公交路线

思路很简单，把一条线路的看作一个集合，然后如果两个集合的交集不为空，就可以连一条线在两条线路中，最初想的是如果求交集可能会超时，之后看到数据范围不大，尝试着去这样做，做好图之后就简单了，所有含有起始点的集合当作起点，所有含有终点的集合当作终点，用Bellman-Ford求即可，最后的答案是在所有终点中取最好的值，还有要注意就是可能不存在起点到终点的路，这时候要返回-1，如果起点就是终点返回0。这道题和今天做的那道PAT的题都用到了求交集，题目我觉得很好，我做了比较长的时间，但是也有很大收获。

class Solution {
public:
    int vis[505];
    int d[505];
    int numBusesToDestination(vector<vector<int>>& routes, int S, int T) {
        set<int> st[505];
        vector<int> G[505];
        int sz=routes.size();
        for(int i=0;i<sz;i++)
        {
            for(int j=0;j<routes[i].size();j++)
            {
                st[i].insert(routes[i][j]);
            }
        }
        for(int i=0;i<sz;i++)
            for(int j=i+1;j<sz;j++)
            {
                auto it1 = st[i].begin(),it2=st[j].begin();
                int ok=0;
                while(it1!=st[i].end()&&it2!=st[j].end())
                {
                    if(*it1<*it2)
                    {
                        it1++;
                    }
                    else if(*it1>*it2)
                    {
                        it2++;
                    }
                    else{
                        ok=1;break;
                    }
                }
                if(ok)
                {
                    G[i].push_back(j);
                    G[j].push_back(i);
                }
            }
        memset(d,0x3f3f3f,sizeof(d));
        queue<int> q;
        for(int i=0;i<sz;i++)
        if(st[i].count(S)!=0)
        {
            q.push(i);
            vis[i]=1;
            d[i]=1;
        }
        int u;
        while(!q.empty())
        {
            u=q.front();q.pop();
            vis[u]=0;
            for(int i=0;i<G[u].size();i++)
            {
                int v=G[u][i];
                if(d[v]>d[u]+1)
                {
                    d[v]=d[u]+1;
                    if(!vis[v])
                    {
                        vis[v]=1;
                        q.push(v);
                    }
                }
            }
        }
        int ans=999;
        for(int i=0;i<sz;i++)
        if(st[i].count(T))
        {
            ans=min(ans,d[i]);
        }
        if(T==S) ans=0;
        if(ans>500) ans=-1;
        return ans;
    }
};