Ideal Path UVA-1599隣接表双方向BFS

考え方:紫書の考え方、まず終点から逆BFSで各点から終点までの最短距離を探し出して、それからBFSに向かって1つの循環内に2つの循環をカバーして、第1の循環は最小の色を探し出して、第2の循環は条件に合う点を類似の行列の配列(vector)に入れてそれからずっと探し出すことができます

#include
using namespace std;
const int maxn=100000+10;

struct Edge{
int u,v,c;
Edge(int a=0,int b=0,int c=0):u(a),v(b),c(c){}
};
vectoredges;   //      
vector G[maxn];
void Add_edges(int u,int v,int c){
edges.push_back(Edge(u,v,c));
int index=edges.size()-1;
G[u].push_back(index);
}

int vis[maxn];
int d[maxn];
int n;



void rev_bfs(){
    memset(vis,0,sizeof(vis));  //   BFS              
d[n-1]=0;
queueq;
q.push(n-1);
vis[n-1]=1;
while(!q.empty()){
    int temp=q.front();
    q.pop();
    for(int i=0;ians;

void bfs(){  //   BFS
memset(vis,0,sizeof(vis));
vis[0]=1;
ans.clear();

vectornext;
next.push_back(0);
for(int i=0;inext2;
    for(int j=0;j