kuangbin_ShortPath N (POJ 1847)

模板题辣很简单的 只有两种val 0 和1

#include <iostream>

#include <string>

#include <cstdio>

#include <cmath>

#include <cstring>

#include <queue>

#include <vector>

#include <set>

#include <algorithm>

#define INF 0x3F3F3F3F

using namespace std;

typedef pair<int, int> pii;

struct cmp{

    bool operator () (const pii a, const pii b){

        return a.first > b.first;

    }

};

int val[][];

int n, a, b;

int dij()

{

    int  dist[];

    priority_queue<pii, vector<pii>, cmp> q;

    memset(dist, 0x3f, sizeof dist);

    dist[a] = ;

    q.push(make_pair(, a));

    while(!q.empty()){

        pii u = q.top();

        q.pop();

        //printf("u.second = %d\n", u.second);

        if(u.first > dist[u.second]) continue;

        for(int i = ; i <= n; i++){

            if(dist[i] > dist[u.second] + val[u.second][i]){

                dist[i] = dist[u.second] + val[u.second][i];

                q.push(make_pair(dist[i], i));

            }

        }

    }

    return dist[b] == INF ? - : dist[b];

}

int main()

{

    memset(val, 0x3f, sizeof val);

    scanf("%d%d%d", &n, &a, &b);

    for(int i = ; i <= n; i++){

        int m, to;

        scanf("%d", &m);

        if(m == ) continue;

        m--;

        scanf("%d", &to);

        val[i][to] = ;

        while(m--){

            scanf("%d", &to);

            val[i][to] = ;

        }

    }

    printf("%d\n", dij());

    return ;

}