問題文

岩井星は町 $1,\ \dots ,\ N$ と特殊な道路 $1,\ \dots,\ M$ からなります。道路 $i$ を通ることで町 $X_i$ から $C_i$ 分掛けて町 $L_i$ から $R_i$ のいずれかへ移動することができます。

岩井星では、ある2つの町の間の移動にかかる最短時間を効率的に求めるアルゴリズムが存在するかは長らく未解決でしたが、29歳の岩井星人さんは町 $1$ から町 $N$ までの移動にかかる最短時間を求めるアルゴリズムを発明したと主張し、「Iwaijkstra法」と名付けて論文を出しました。

Iwaijkstra法

$\mathrm{que}$を優先度付きキューとし、数字のペア$(0,1)$を追加する
$\mathrm{dist}$を長さ$N$の配列とし、$\mathrm{dist}_1$に0を、それ以外の要素に$\inf$を代入する
$\mathrm{vis}$を長さ$N$の配列とし、全ての要素にfalseを代入する
$\mathrm{que}$が空になるまで繰り返す
    $\mathrm{que}$の中の数字のペアのうち左側の要素が最小となる数字のペア(そのような要素が複数存在する場合は、さらに右側の要素が最小となるペア)の1つを$(a,b)$として記憶する
    $\mathrm{que}$から数字のペア$(a,b)$を1つ削除する
    $\mathrm{dist}_i < a$となる全てのiにおいて$\mathrm{vis}_i$にtrueを代入する
    $\mathrm{dist}_b = a$ならば、
        $X_j = b$ となる全ての$j$において、また $L_j \leq k \leq R_j$ となる全ての$k$において、$\mathrm{vis}_k =\ $false ならば、
            $\mathrm{dist}_k$に$\min(\mathrm{dist}_k,a+C_j)$を代入し、$\mathrm{que}$に数字のペア$(a+C_j,k)$を追加する
$\mathrm{dist}_N$を出力する

岩井星人さんは、ほとんど全ての操作を一瞬で完了することができますが、唯一、$\mathrm{que}$からの削除の処理はとても複雑なため時間がかかることに気付きました。

岩井星人さんに代わって、岩井星でこのアルゴリズムを実行したときに何回$\mathrm{que}$からの削除を行なうか求めてください。ただし、この回数が$10^{18}$を超えるとき、またはこのアルゴリズムが停止しないときはToo Manyと出力してください。

Iwaijkstra法の実装例

#include <bits/stdc++.h>
using namespace std;

long long iwaijkstra(int n, int m, vector<int> x, vector<int> l, vector<int> r, vector<int> c){
	multiset<pair<long long, int>> que;
	que.emplace(0, 1);
	vector<long long> dist(n, 1e18), vis(n);
	dist[0] = 0;
	int ans(0);
	while(!que.empty()){
		auto [a, b] = *que.begin();
		que.erase(que.begin()), ++ans;
		for (int i(0); i < n; ++i) if (dist[i] < a) vis[i] = true;
		if (vis[b - 1]) continue;
		for (int i(0); i < m; ++i) if (x[i] == b){
			for (int j(l[i] - 1); j < r[i]; ++j) if (!vis[j]) {
			    dist[j] = min(dist[j], a + c[i]);
			    que.emplace(a + c[i], j + 1);
			}
		}
	}
	cout << ans << endl;
	return dist.back();
}

import heapq

def iwaijkstra(n,m,x,l,r,c):
    que = []
    heapq.heappush(que, (0, 1))
    dist = [10 ** 18] * n
    dist[0] = 0
    vis = [False] * n
    ans = 0
    while len(que) > 0:
        a, b = que[0]
        heapq.heappop(que)
        ans += 1
        for i in range(n):
            if dist[i] < a:
                vis[i] = True
        if vis[b-1]: continue
        for i in range(m):
            if x[i] == b:
                for j in range(l[i] - 1, r[i]):
                    if not vis[j]:
                        dist[j] = min(dist[j], a + c[i])
                        heapq.heappush(que, (a + c[i], j + 1))
    print(ans)
    return dist[n-1]

制約

• $1 \le N,M \le 10^5$
• $1 \le X_i \le N$
• $1 \le L_i \le R_i \le N$
• $0 \le C_i \le 10^9$
• 入力は全て整数
• 頂点1から全ての頂点に到達することができる

入力

$N\ M$
$X_1\ L_1\ R_1\ C_1$
$\vdots$
$X_M\ L_M\ R_M\ C_M$

出力

最後に改行してください。

サンプル

サンプル1

入力

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

出力

7

岩井星の町と道路をグラフにすると、以下のようになります。

このグラフでの辺の色と道路の番号の対応は赤が1、緑が2、青が3、黄色が4です。

サンプル2

入力

6 4
1 4 6 1
4 2 3 0
3 5 6 8
2 3 3 0

出力

11

辺の色と道路の番号の対応はサンプル1と同じです。

6 7
1 1 6 4
1 1 6 0
2 4 4 0
4 6 6 0
6 3 3 0
3 5 5 0
5 2 2 0

Too Many

20 19
1 2 20 0
2 3 20 0
3 4 20 0
4 5 20 0
5 6 20 0
6 7 20 0
7 8 20 0
8 9 20 0
9 10 20 0
10 11 20 0
11 12 20 0
12 13 20 0
13 14 20 0
14 15 20 0
15 16 20 0
16 17 20 0
17 18 20 0
18 19 20 0
19 20 20 0

524288