leetcode-go/poj/3967.ideal-path/main.cc

#include <cstdio>
#include <cstring>
#include <vector>
#include <queue>

using std::vector; using std::queue;

const int N = 100000;
const int M = 200000;
const int C = 1000000000;

struct node {
    int x;
    int y;
    node(int x, int y) : x(x), y(y) {}
};

vector<node> g[N + 1];

int dis[N + 1];

int main() {
    int n, m;
    scanf("%d %d", &n, &m);
    for (int i = 0, p, q, c; i < m; i++) {
        scanf("%d %d %d", &p, &q, &c);
        if (p == q) continue;
        g[p].push_back(node(q, c));
        g[q].push_back(node(p, c));
    }
    memset(dis, -1, sizeof(dis));
    queue<int> q;
    q.push(n);
    dis[n] = 0;
    int d = 0, size = q.size();
    while (size != 0) {
        int cur = q.front();
        q.pop();
        if (cur == 1) break;
        size--;
        for (node i : g[cur]) {
            if (dis[i.x] == -1) {
                dis[i.x] = d + 1;
                q.push(i.x);
            }
        }
        if (size == 0) {
            size = q.size();
            d++;
        }
    }
    printf("%d\n", d);
    q = queue<int>();
    q.push(1);
    while (!q.empty()) {
        int cur = q.front();
        q.pop();
        if (cur == n) break;
    }
    return 0;
}