1077.安全网络 ver.4

#include <cstdio>
#include <cstdlib>
#include <iostream>
#include <vector>
#include <queue>
#define inf 0x3fffffff
using namespace std;

struct node {
    node(int num, int len) {
        this->num = num;
        this->len = len;
    }
    int num;
    int len;
};

vector<node> nt[100001];
bool b[100001];
int d[100001];
int n;

int spfa() {
    queue<int> que;
    for (int i = 2; i <= n; i++) {
        d[i] = inf;
        b[i] = false;
    }
    d[1] = 0;
    b[1] = true;
    que.push(1);
    while (!que.empty()) {
        int u = que.front();
        que.pop();
        b[u] = false;
        for (vector<node>::iterator it = nt[u].begin(); it != nt[u].end(); it++) {
            if (d[it->num] > d[u] + it->len) {
                d[it->num] = d[u] + it->len;
                if (!b[it->num]) {
                    b[it->num] = true;
                    que.push(it->num);
                }
            }
        }
    }
    return d[n] != inf ? d[n] : -1;
}

int main(int argc, char* argv[]) {
    int m, u, v, len;

    scanf("%d %d", &n, &m);
    while (m--) {
        scanf("%d %d %d", &u, &v, &len);
        nt[u].push_back(node(v, len));
        nt[v].push_back(node(u, len));
    }
    printf("%d\n", spfa());

    return 0;
}