Age of Moyu

Mr.Quin love fishes so much and Mr.Quin’s city has a nautical system,consisiting of N ports and M shipping lines. The ports are numbered 1 to N. Each line is occupied by a Weitian. Each Weitian has an identification number.

The i-th (1≤i≤M) line connects port Ai and Bi (Ai≠Bi) bidirectionally, and occupied by Ci Weitian (At most one line between two ports).

When Mr.Quin only uses lines that are occupied by the same Weitian, the cost is 1 XiangXiangJi. Whenever Mr.Quin changes to a line that is occupied by a different Weitian from the current line, Mr.Quin is charged an additional cost of 1 XiangXiangJi. In a case where Mr.Quin changed from some Weitian A’s line to another Weitian’s line changes to Weitian A’s line again, the additional cost is incurred again.

Mr.Quin is now at port 1 and wants to travel to port N where live many fishes. Find the minimum required XiangXiangJi (If Mr.Quin can’t travel to port N, print −1 instead)
Input
There might be multiple test cases, no more than 20. You need to read till the end of input.

For each test case,In the first line, two integers N (2≤N≤100000) and M (0≤M≤200000), representing the number of ports and shipping lines in the city.

In the following m lines, each contain three integers, the first and second representing two ends Ai and Bi of a shipping line (1≤Ai,Bi≤N) and the third representing the identification number Ci (1≤Ci≤1000000) of Weitian who occupies this shipping line.
Output
For each test case output the minimum required cost. If Mr.Quin can’t travel to port N, output −1 instead.

Sample Input
3 3 
1 2 1
1 3 2
2 3 1
2 0
3 2
1 2 1
2 3 2
Sample Output
1
-1
2

#include <bits/stdc++.h>

using namespace std;
const int N = 1e5 + 10, M = 4e5 + 10;
int head[N], ver[M], Next[M], edge[M], tot;
int d[N];
int n, m;
set<int> st[N];

struct node {
    int d, u, pre, fa;

    bool operator<(const node &a) const {
        return d > a.d;
    }
};

void add(int x, int y, int z) {
    ver[++tot] = y;
    edge[tot] = z;
    Next[tot] = head[x];
    head[x] = tot;
}

inline void init() {
    memset(head, 0, sizeof(head));
    memset(Next, 0, sizeof(Next));
    memset(d, 0x3f, sizeof(d));
    for (int i = 1; i <= n; i++)st[i].clear();
    tot = 0;
}

inline void read() {
    for (int i = 1; i <= m; i++) {
        int x, y, z;
        scanf("%d%d%d", &x, &y, &z);
        add(x, y, z);
        add(y, x, z);
    }
}

inline void dijkstra() {
    priority_queue<node> q;
    d[1] = 0;
    q.push({0, 1, -1, -1});
    while (!q.empty()) {
        node t = q.top();
        q.pop();
        if (t.d > d[t.u])continue;
        else if (t.d == d[t.u]) {
            if (st[t.u].count(t.pre))continue;
            st[t.u].insert(t.pre);
        }
        for (int i = head[t.u]; i; i = Next[i]) {
            int v = ver[i], now = edge[i];
            if (t.fa == v)continue;
            if (d[v] > d[t.u] + (t.pre != now)) {
                d[v] = d[t.u] + (t.pre != now);
                st[v].clear();
                q.push({d[v], v, now, t.u});
            } else if (d[v] == d[t.u] + (t.pre != now))
                q.push({d[v], v, now, t.u});
        }
    }
    if (d[n] == 0x3f3f3f3f)printf("-1\n");
    else printf("%d\n", d[n]);
}

int main() {
    while (scanf("%d%d", &n, &m) != EOF) {
        init();
        read();
        dijkstra();
    }
    return 0;
}