使用最短路之前居然忘记清空了。

#include
    
     using namespace std;typedef long long ll;const int MAXN = 1005;int n, s, t;int dis[MAXN];bool vis[MAXN];int G[MAXN][MAXN];const int INF = 0x3f3f3f3f;priority_queue
     
      
        >pq;void Dijkstra(int s) {    for(int i=1;i<=n;++i)        dis[i]=INF;    dis[s] = 0;    pq.push({-dis[s], s});    while(!pq.empty()) {        int u = pq.top().second;        pq.pop();        if(vis[u])            continue;        /*printf("u=%d\n",u);        for(int i = 1; i <= n; ++i) {            printf(" %d", i, dis[i]);        }        puts("");*/        vis[u] = 1;        for(int v = 1; v <= n; ++v) {            int w = G[u][v];            if(!vis[v] && dis[u] + w < dis[v]) {                dis[v] = dis[u] + w;                pq.push({-dis[v], v});            }        }    }}int main() {#ifdef Yinku    freopen("Yinku.in", "r", stdin);#endif // Yinku    scanf("%d%d%d", &n, &s, &t);    for(int i = 1; i <= n; ++i)        for(int j = 1; j <= n; ++j)            G[i][j] = INF;    for(int i = 1; i <= n; ++i)        G[i][i] = 0;    for(int u = 1; u <= n; ++u) {        int k;        scanf("%d", &k);        for(int j = 1; j <= k; ++j) {            int v;            scanf("%d", &v);            if(j == 1)                G[u][v] = 0;            else                G[u][v] = 1;        }    }    Dijkstra(s);    /*for(int i = 1; i <= n; ++i) {        printf("%d: %d\n", i, dis[i]);    }*/    printf("%d\n", dis[t] < INF ? dis[t] : -1);    return 0;}
      
     
    

看了一下题解貌似还有更快的。

#include
    
     using namespace std;typedef long long ll;const int MAXN = 1005;int n, s, t;int dis[MAXN];bool vis[MAXN];int G[MAXN][MAXN];const int INF = 0x3f3f3f3f;deque
     
      q;void BFS(int s) {    for(int i = 1; i <= n; ++i)        dis[i] = INF;    dis[s] = 0;    q.push_front(s);    while(!q.empty()) {        int u = q.front();        q.pop_front();        if(vis[u])            continue;        vis[u] = 1;        for(int v = 1; v <= n; ++v) {            if(vis[v])                continue;            int w = G[u][v];            if(w == 0) {                if(dis[u] < dis[v]) {                    dis[v] = dis[u];                    q.push_front(v);                }            } else if(w == 1) {                if(dis[u] + 1 < dis[v]) {                    dis[v] = dis[u] + 1;                    q.push_back(v);                }            }        }    }}int main() {#ifdef Yinku    freopen("Yinku.in", "r", stdin);#endif // Yinku    scanf("%d%d%d", &n, &s, &t);    for(int i = 1; i <= n; ++i)        for(int j = 1; j <= n; ++j)            G[i][j] = INF;    for(int i = 1; i <= n; ++i)        G[i][i] = 0;    for(int u = 1; u <= n; ++u) {        int k;        scanf("%d", &k);        for(int j = 1; j <= k; ++j) {            int v;            scanf("%d", &v);            G[u][v] = (j != 1);        }    }    BFS(s);    printf("%d\n", dis[t] < INF ? dis[t] : -1);    return 0;}
     
    

那应该可以得到一个使得Dijkstra更快的办法，就是另外开一个队列，把u节点相连的距离为0的节点加入队列，每次优先从队列里面取，其次才从优先队列里面取。

这个01BFS是指有花费的边的权都一样，所以不需要优先队列，从u出发的能到的点假如有花费一定是出现在队尾的。