学步园

#define maxnode 105
#define maxn 1<<29
int n , d[maxnode];
bool inq[maxnode];
int cnt[maxnode];
struct edge
{
    int from , to, dist;
};
vector<edge> edges;
vector<int> g[maxnode];
void addedge( int from, int to, int dist)
{
    edges.push_back(( edge ){ from, to, dist });
    g[from].push_back( edges.size() - 1 );
}
void init( int num )
{
    for(int i=1 ; i<=num ; i++ )g[i].clear();
    edges.clear();
    memset( cnt , 0 , sizeof( cnt ));
}
bool spfa( int s ,int  t )
{
    queue<int> q;
    for(int i=1 ; i<=n ; i++ )d[i]=maxn;
    d[1]=0;
    q.push(s);
    inq[s] = true;
    while( !q.empty() )
    {
        int u = q.front();
        q.pop();
        inq[u] = false ;
        int size = g[u].size();
        for(int i=0 ; i< size ; i++ )
        {
            edge &e =edges[g[u][i]];
            if( d[e.to] > d[u] + e.dist )
            {
                d[e.to] = d[u] + e.dist ;
                if(!inq[e.to])
                {
                    q.push( e.to );
                    inq[e.to] = true;
                    if( ++cnt[e.to]>n )return false;
                }
            }
        }
    }
    return true ;
}