Problem:


Score : 600 points

Problem Statement

Snuke's town has a subway system, consisting of N stations and M railway lines. The stations are numbered 1 through N. Each line is operated by a company. Each company has an identification number.

The i-th ( 1 \leq i \leq M ) line connects station p_i and q_i bidirectionally. There is no intermediate station. This line is operated by company c_i.

You can change trains at a station where multiple lines are available.

The fare system used in this subway system is a bit strange. When a passenger only uses lines that are operated by the same company, the fare is 1 yen (the currency of Japan). Whenever a passenger changes to a line that is operated by a different company from the current line, the passenger is charged an additional fare of 1 yen. In a case where a passenger who changed from some company A's line to another company's line changes to company A's line again, the additional fare is incurred again.

Snuke is now at station 1 and wants to travel to station N by subway. Find the minimum required fare.

Constraints

2 \leq N \leq 10^5

0 \leq M \leq 2×10^5

1 \leq p_i \leq N (1 \leq i \leq M)

1 \leq q_i \leq N (1 \leq i \leq M)

1 \leq c_i \leq 10^6 (1 \leq i \leq M)

p_i \neq q_i (1 \leq i \leq M)

Input

The input is given from Standard Input in the following format:

N M
p_1 q_1 c_1
:
p_M q_M c_M

Output

Print the minimum required fare. If it is impossible to get to station N by subway, print -1 instead.

Sample Input 1

3 3
1 2 1
2 3 1
3 1 2

Sample Output 1

1

Use company 1's lines: 1 → 2 → 3. The fare is 1 yen.

Sample Input 2

8 11
1 3 1
1 4 2
2 3 1
2 5 1
3 4 3
3 6 3
3 7 3
4 8 4
5 6 1
6 7 5
7 8 5

Sample Output 2

2

First, use company 1's lines: 1 → 3 → 2 → 5 → 6. Then, use company 5's lines: 6 → 7 → 8. The fare is 2 yen.

Sample Input 3

2 0

Sample Output 3

-1



Sample input:
3 3
1 2 1
2 3 1
3 1 2


Sample output:
1

Submission status: Runtime Error

Solution code:
#include <iostream>
#include <fstream>
#include <string> 
#include <cmath>  
#include <cstdlib>
#include <ctime>
#include <vector>
#include <algorithm>
#include <numeric>
#include <map>
#include <set>
#include <stack>
#include <queue>
#include <deque>
#include <functional>

using namespace std;
using ll = long long;
using ull = unsigned long long;

#define FOR(i, m, n) for(int i = int(m);i < int(n);i++)
#define REFOR(i, m, n) for(int i = int(n - 1);i >= int(m);i--)
#define REP(i,n) for(int i = 0; i < int(n); i++)
#define REREP(i,n) for(int i = int(n - 1); i >= 0; i--)
#define VI vector<int>
#define VVI vector<vector<int>>
#define VVVI vector<vector<vector<int>>>
#define VL vector<ll>
#define VVL vector<vector<ll>>
#define VB vector<bool>
#define VVB vector<vector<bool>>
#define PAIR pair<int,int>
#define MP make_pair
#define VP vector<pair<int,int>>
#define VS vector<string>
#define MAP map<int,int>
#define QUE queue<int>
#define DEQ deque<int>
#define PQUE priority_queue<int> //5,5,4,3,3,2,...
#define REPQUE priority_queue<int, vector<int>, greater<int>> //1,1,2,3,4,4,5,...
#define SUM(obj) accumulate((obj).begin(), (obj).end(), 0)
#define SORT(obj) sort((obj).begin(), (obj).end()) // 1,2,3,4,5...
#define RESORT(obj) sort((obj).begin(), (obj).end(), greater<int>()) // 5,4,3,2,1...
#define UB(obj,n) upper_bound((obj).begin(), (obj).end(), n) //itr > n
#define LB(obj,n) lower_bound((obj).begin(), (obj).end(), n) //itr>= n

const ll MOD = (ll)1e9 + 7;
const ll INF = (ll)1e17;


void ANS(bool flag){
	cout << ((flag) ? "YES" : "NO") << endl;
}

void Ans(bool flag) {
	cout << ((flag) ? "Yes" : "No") << endl;
}

void ans(bool flag) {
	cout << ((flag) ? "yes" : "no") << endl;
}

struct EDGE {
	int fromtrain, to, totrain, cost;
};

vector<vector<PAIR>> edge(100000 + 1);
vector<vector<PAIR>> node(100000 + 1);

void dijkstra(void) {
	priority_queue<pair<int,PAIR>, vector<pair<int,PAIR>>, greater<pair<int,PAIR>>> pq;
	set<PAIR> st;
	node[1][0].second = 0;
	pq.push({ 0,{1, 0}});

	while (!pq.empty()) {
		int from = pq.top().second.first;
		int i = pq.top().second.second;
		pq.pop();

		if (i == 0) {
			REP(j, edge[from].size()) {
				int to = edge[from][j].first;
				int train = edge[from][j].second;
				FOR(k, 1, node[to].size()) {
					if (node[to][k].first == train && node[to][k].second > node[from][0].second + 1) {
						node[to][k].second = node[from][0].second + 1;
						pq.push({ node[to][k].second,{ to , k } });
					}
				}
			}
		}
		else {
			if (node[from][0].second > node[from][i].second) {
				node[from][0].second = node[from][i].second;
				pq.push({ node[from][0].second,{ from , 0 } });
			}
			REP(j, edge[from].size()) {
				int to = edge[from][j].first;
				int train = edge[from][j].second;
				if (node[from][i].first == train) {
					FOR(k, 1, node[to].size()) {
						if (node[to][k].first == node[from][i].first && node[to][k].second > node[from][i].second) {
							node[to][k].second = node[from][i].second;
							pq.push({ node[to][k].second,{ to , k } });
						}
					}
				}
			}
		}
	}
	return;
}

int main() {
	int N, M;
	cin >> N >> M;
	FOR(i, 1, N + 1) node[i].push_back({ -1, 10000000 });

	set<PAIR> st;
	REP(i, M) {
		int p, q, c;
		cin >> p >> q >> c;
		if (st.insert({ p,c }).second) node[p].push_back({ c, 10000000 });
		if (st.insert({ q,c }).second) node[q].push_back({ c, 10000000 });
		edge[p].push_back({q,c});
		edge[q].push_back({p,c});
	}

	if (M == 0) {
		cout << -1 << endl;
		return 0;
	}

	dijkstra();
	//FOR(i, 1, N + 1) {
	//	cout << i << "  ";
	//	REP(j, node[i].size()){
	//		cout << node[i][j].first << " " << node[i][j].second << "   ";
	//	}
	//	cout << endl;
	//}

	
	cout << node[N][0].second << endl;
	//cin >> N >> M;


	return 0;
}

Submission status: Runtime Error

Solution code:
import numpy as np

N, M = map(int, input().split())
routes = np.array([list(map(int, input().split())) for _ in range(M)], 'i')
queue = [(1, 0, 0)]
dist = np.zeros(N + 1, 'i')
dist[:] = 10000

while len(queue) > 0:
    start, lastm, cost = queue[0]
    del queue[0]
    if start == N:
        print(cost)
        exit()
    if cost > dist[start]:
        continue
    dist[start] = cost

    for (f, t, m) in routes[routes[:, 0] == start]:
        if m == lastm:
            queue.insert(0, (t, m, cost))
        else:
            queue.append((t, m, cost + 1))

print(-1)

Submission status: Runtime Error

Solution code:
import numpy as np

N, M = map(int, input().split())
routes = np.array([list(map(int, input().split())) for _ in range(M)], 'i')
queue = [(1, 0, 0)]

while len(queue) > 0:
    start, lastm, cost = queue[0]
    del queue[0]
    if start == N:
        print(cost)
        exit()

    for (f, t, m) in routes[routes[:, 0] == start]:
        if m == lastm:
            queue.insert(0, (t, m, cost))
        else:
            queue.append((t, m, cost + 1))

print(-1)

Submission status: Runtime Error

Solution code:
import numpy as np

N, M = map(int, input().split())
routes = np.array([list(map(int, input().split())) for _ in range(M)], 'i')

# i駅まで到達したときの最小コスト（最終電車がjで示される）
dp = [{} for _ in range(N + 1)]
dp[1][0] = 0

for i in range(2, N + 1):
    for (f, t, m) in routes[routes[:, 1] == i]:
        if m in dp[f]:
            dp[t][m] = dp[f][m]
        else:
            values = dp[f].values()
            if len(values) > 0:
                dp[t][m] = min(values) + 1

if len(dp[N].values()) > 0:
    print(min(dp[N].values()))
else:
    print(-1)

Submission status: Runtime Error

Solution code:
import numpy as np

N, M = map(int, input().split())
routes = np.array([list(map(int, input().split())) for _ in range(M)], 'i')
#print(routes)

# i駅まで到達したときの最小コスト（最終電車がjで示される）
dp = np.zeros((N + 1, M + 1), 'i')
dp[:, :] = 10000
dp[1, 0] = 0

for i in range(2, N + 1):
    for (f, t, m) in routes:
        if t != i:
            continue

        if dp[f, m] < 10000:
            dp[t, m] = dp[f, m]
        else:
            dp[t, m] = min(dp[f, :]) + 1

cost = min(dp[N, :])
if cost < 10000:
    print(cost)
else:
    print(-1)

Submission status: Runtime Error

Solution code:
import numpy as np

N, M = map(int, input().split())
routes = np.array([list(map(int, input().split())) for _ in range(M)], 'i')
print(routes)

# i駅まで到達したときの最小コスト（最終電車がjで示される）
dp = np.zeros((N + 1, M + 1), 'i')
dp[:, :] = 10000
dp[1, 0] = 0

for i in range(2, N + 1):
    for (f, t, m) in routes:
        if t != i:
            continue

        if dp[f, m] < 10000:
            dp[t, m] = dp[f, m]
        else:
            dp[t, m] = min(dp[f, :]) + 1

cost = min(dp[N, :])
if cost < 10000:
    print(cost)
else:
    print(-1)