結果
| 問題 | No.3111 Toll Optimization |
| コンテスト | |
| ユーザー |
 おおえはるき
|
| 提出日時 | 2026-04-11 13:25:34 |
| 言語 | C++23 (gcc 15.2.0 + boost 1.89.0) |
| 結果 |
AC
|
| 実行時間 | 180 ms / 5,000 ms |
| コード長 | 24,896 bytes |
| 記録 | |
| コンパイル時間 | 3,628 ms |
| コンパイル使用メモリ | 366,136 KB |
| 実行使用メモリ | 49,448 KB |
| 最終ジャッジ日時 | 2026-04-11 13:25:56 |
| 合計ジャッジ時間 | 13,355 ms |
|
ジャッジサーバーID （参考情報） |
judge3_0 / judge2_1 |
（要ログイン）
| ファイルパターン | 結果 |
|---|---|
| sample | AC * 3 |
| other | AC * 70 |
ソースコード
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using str = string;
static int intMin = numeric_limits<int>::min();
static int intMax = numeric_limits<int>::max();
static long long longMin = numeric_limits<long long>::min();
static long long longMax = numeric_limits<long long>::max();
const ll INF = 1e9 + 7;
static ll mod = 998244353;
static long long di[] = { -1, 0, 1, 0, -1, -1, 1, 1};
static long long dj[] = { 0, 1, 0, -1, -1, 1, -1, 1};
class ReadArray { public:
vector<int> in() { string s; getline(cin >> ws, s); istringstream is(s); return vector<int>(istream_iterator<int>(is), {}); }
vector<long long> ll() { string s; getline(cin >> ws, s); istringstream is(s); return vector<long long>(istream_iterator<long long>(is), {}); }
vector<float> fl() { string s; getline(cin >> ws, s); istringstream is(s); return vector<float>(istream_iterator<float>(is), {}); }
vector<double> dbl() { string s; getline(cin >> ws, s); istringstream is(s); return vector<double>(istream_iterator<double>(is), {}); }
vector<string> str() { string s; getline(cin >> ws, s); istringstream is(s); return vector<string>(istream_iterator<string>(is), {}); }
vector<char> ch() { string s; getline(cin >> ws, s); istringstream is(s); vector<char> v; for (char c; is >> c;) v.push_back(c); return v; }
}; ReadArray readArray;
class ReadMap { public:
vector<vector<int>> in(int h, int w) { vector<vector<int>> r(h,vector<int>(w)); for(int i=0;i<h;i++){auto s = readArray.in(); for(int j=0;j<w;j++) r.at(i).at(j)=s.at(j);} return r; }
vector<vector<long long>> ll(int h, int w) { vector<vector<long long>> r(h,vector<long long>(w)); for(int i=0;i<h;i++){auto s = readArray.ll(); for(int j=0;j<w;j++) r.at(i).at(j)=s.at(j);} return r; }
vector<vector<char>> ch(int h, int w) { vector<vector<char>> r(h,vector<char>(w)); for(int i=0;i<h;i++){string s; cin >> s; for(int j=0;j<w;j++) r.at(i).at(j)=s.at(j);} return r; }
vector<vector<bool>> bo(int h, int w, char c = '.') { vector<vector<bool>> r(h,vector<bool>(w)); for(int i=0;i<h;i++){string s; cin >> s; for(int j=0;j<w;j++) r.at(i).at(j)=(s.at(j)==c);} return r;}
};
class ReadFunctions { public:
int in() { int x; scanf("%d", &x); return x; }
auto in2() { int x, y; scanf("%d %d", &x, &y); return make_tuple(x, y); }
auto in3() { int x, y, z; scanf("%d %d %d", &x, &y, &z); return make_tuple(x, y, z); }
auto in4() { int x, y, z, w; scanf("%d %d %d %d", &x, &y, &z, &w); return make_tuple(x, y, z, w); }
auto in5() { int x, y, z, w, u; scanf("%d %d %d %d %d", &x, &y, &z, &w, &u); return make_tuple(x, y, z, w, u); }
auto in6() { int x, y, z, w, u, v; scanf("%d %d %d %d %d %d", &x, &y, &z, &w, &u, &v); return make_tuple(x, y, z, w, u, v); }
long long ll() { long long x; scanf("%lld", &x); return x; }
auto ll2() { long long x, y; scanf("%lld %lld", &x, &y); return make_tuple(x, y); }
auto ll3() { long long x, y, z; scanf("%lld %lld %lld", &x, &y, &z); return make_tuple(x, y, z); }
auto ll4() { long long x, y, z, w; scanf("%lld %lld %lld %lld", &x, &y, &z, &w); return make_tuple(x, y, z, w); }
auto ll5() { long long x, y, z, w, u; scanf("%lld %lld %lld %lld %lld", &x, &y, &z, &w, &u); return make_tuple(x, y, z, w, u); }
auto ll6() { long long x, y, z, w, u, v; scanf("%lld %lld %lld %lld %lld %lld", &x, &y, &z, &w, &u, &v); return make_tuple(x, y, z, w, u, v); }
float fl() { float x; scanf("%f", &x); return x; }
double dbl() { double x; scanf("%lf", &x); return x; }
string str() { string x; cin >> x; return x; }
char cha() { char x; scanf(" %c", &x); return x; }
ReadArray array;
ReadMap map;
}; ReadFunctions re;
void write(string s) { printf("%s\n", s.c_str()); }
void write(char c) { printf("%c\n", c); }
void write(int n) { printf("%i\n", n); }
void write(long long n) { printf("%lld\n", n); }
void write(double n) { printf("%.10f\n", n); }
void write(bool a) { printf("%s\n", a ? "Yes" : "No"); }
void writeMinus1() {printf("%i\n", -1);}
/* keysにそってvalueをソート */
template <typename T> void Sort(std::vector<T>& keys, std::vector<T>& values) {
std::vector<std::pair<T, T>> paired;
for (size_t i = 0; i < keys.size(); ++i) {
paired.emplace_back(keys[i], values[i]);
}
std::sort(paired.begin(), paired.end());
for (size_t i = 0; i < keys.size(); ++i) {
keys[i] = paired[i].first;
values[i] = paired[i].second;
}
}
template <typename T> void Sort(vector<T> &array) {sort(array.begin(), array.end());}
template <typename T> void Reverse(vector<T> &array) {reverse(array.begin(), array.end());}
struct pair_hash {
template <class T1, class T2>
size_t operator()(const pair<T1, T2>& p) const {
auto h1 = hash<T1>{}(p.first);
auto h2 = hash<T2>{}(p.second);
return h1 ^ (h2 << 1); // XORとビットシフトを利用してハッシュを合成
}
};
struct tuple_hash {
template <typename... T>
size_t operator()(const tuple<T...>& t) const {
size_t seed = 0;
apply([&seed](const auto&... args) {
((seed ^=
hash<decay_t<decltype(args)>>{}(args)
+ 0x9e3779b97f4a7c15ULL
+ (seed << 6)
+ (seed >> 2)
), ...);
}, t);
return seed;
}
};
long long average(long long a, long long b) {return a + (b - a) / 2; }
long long kaijou(long long v) { long long r = 1; for (long long i = v; i > 0; i--) r *= i; return r; }
long long yojou(int v, int v2) { long long r = v % v2; return r < 0 ? r + v2 : r; }
long long yojou(ll v, ll v2) { long long r = v % v2; return r < 0 ? r + v2 : r; }
int digit_count(long long n) {if(n==0)return 1;n=llabs(n);int cnt=0;while(n>0){cnt++;n/=10;}return cnt;}
bool rangeCheck(int i, int j, int h, int w) { return (0 <= i && i < h && 0 <= j && j < w);}
long long power(long long base, long long exp) { long long result = 1; for (int i = 0; i < exp; ++i) result *= base; return result; }
long long modPow(long long r, long long n) {long long res = 1; r %= mod; while (n > 0) { if (n & 1) res *= r; res %= mod; r *= r; r %= mod; n >>= 1;} return res % mod;}
long long modinv(long long a) { ll b = mod, u = 1, v = 0; while (b) { ll t = a / b; a -= t * b; swap(a, b); u -= t * v; swap(u, v); } u %= mod; if (u < 0) u += mod; return u; }
int popcount(ll num) {int count = 0;while(num){count+=num&1;num>>=1;}return count;}
long long GCD(long long a, long long b) {if(b==0)return a;return GCD(b,a%b);}
mt19937 rng(123456); // 固定seed（好きな数字でOK）
// [l, r] の整数乱数
int rand_int(int l, int r) {
uniform_int_distribution<int> dist(l, r);
return dist(rng);
}
// [0, 1) の実数乱数
double rand_double() {
uniform_real_distribution<double> dist(0.0, 1.0);
return dist(rng);
}
struct UnionFind {
vector<int> parent, rank, parity;
// parity[x] : 親との色差（0=同色, 1=異色）
UnionFind(int n) {
parent.resize(n);
rank.resize(n, 0);
parity.resize(n, 0);
for(int i = 0; i < n; i++) parent[i] = i;
}
pair<int,int> find(int x) {
if(parent[x] == x) return {x, 0};
auto [r, p] = find(parent[x]);
parity[x] ^= p;
parent[x] = r;
return {parent[x], parity[x]};
}
// 戻り値: {親になった根, 子になった根, 子を反転する必要があるか}
tuple<int,int,bool> unite(int x, int y) {
auto [rx, px] = find(x);
auto [ry, py] = find(y);
if(rx == ry) {
return {rx, ry, false};
}
bool needFlip = ((px ^ py) == 0);
if(rank[rx] < rank[ry]) {
swap(rx, ry);
swap(px, py);
}
parent[ry] = rx;
parity[ry] = px ^ py ^ 1;
if(rank[rx] == rank[ry]) rank[rx]++;
return {rx, ry, needFlip};
}
};
template <typename T> int FindEqual(vector<T> &vec, T target) {
int l = 0; int r = vec.size()-1;
int ret = -1;
while(l <= r) {
int mid = (l + r)/2;
if(vec.at(mid) > target) {
r = mid - 1;
}
else if(vec.at(mid) == target)
{
ret = mid;
break;
}
else l = mid + 1;
}
return ret;
}
template <typename T> int FindFirstGreater(vector<T> &vec, T target) {
int l = 0; int r = vec.size()-1;
int ret = -1;
while(l <= r) {
int mid = (l + r)/2;
if(vec.at(mid) >= target) {
ret = mid;
r = mid - 1;
}
else l = mid + 1;
}
return ret;
}
template <typename T> int FindFirstLess(vector<T> &vec, T target) {
int l = 0; int r = vec.size()-1;
int ret = -1;
while(l <= r) {
int mid = (l + r)/2;
if(vec.at(mid) <= target) {
ret = mid;
l = mid + 1;
}
else r = mid - 1;
}
return ret;
}
class SegmentTreeSum {
private:
std::vector<long long> tree; // セグメントツリー
int size; // 配列のサイズ
// セグメントツリーの構築
void build(const std::vector<int>& arr, int node, int start, int end) {
if (start == end) {
// 葉ノードの場合
tree[node] = arr[start];
} else {
int mid = (start + end) / 2;
// 左右の子ノードを再帰的に構築
build(arr, 2 * node + 1, start, mid);
build(arr, 2 * node + 2, mid + 1, end);
// 子ノードをマージ
tree[node] = tree[2 * node + 1] + tree[2 * node + 2];
}
}
// 範囲クエリ
long long query(int node, int start, int end, int l, int r) {
if (r < start || end < l) {
// 範囲外の場合
return 0;
}
if (l <= start && end <= r) {
// 完全に範囲内の場合
return tree[node];
}
// 範囲が部分的に重なる場合
int mid = (start + end) / 2;
long long leftSum = query(2 * node + 1, start, mid, l, r);
long long rightSum = query(2 * node + 2, mid + 1, end, l, r);
return leftSum + rightSum;
}
// 値の更新
void update(int node, int start, int end, int idx, int val) {
if (start == end) {
// 葉ノードを更新
tree[node] = val;
} else {
int mid = (start + end) / 2;
if (start <= idx && idx <= mid) {
// 左部分木を更新
update(2 * node + 1, start, mid, idx, val);
} else {
// 右部分木を更新
update(2 * node + 2, mid + 1, end, idx, val);
}
// 子ノードの値を基に現在のノードを更新
tree[node] = tree[2 * node + 1] + tree[2 * node + 2];
}
}
public:
// コンストラクタ: 配列を受け取り、セグメントツリーを構築
SegmentTreeSum(const std::vector<int>& arr) {
size = arr.size();
tree.resize(4 * size);
build(arr, 0, 0, size - 1);
}
// 範囲クエリの公開メソッド
long long query(int l, int r) {
return query(0, 0, size - 1, l, r);
}
// 値の更新の公開メソッド
void update(int idx, int val) {
update(0, 0, size - 1, idx, val);
}
};
class SegmentTreeMax {
private:
std::vector<long long> tree; // セグメントツリー（区間の最大値）
int size; // 配列のサイズ
// セグメントツリーの構築
void build(const std::vector<long long>& arr, int node, int start, int end) {
if (start == end) {
// 葉ノードの場合
tree[node] = arr[start];
} else {
int mid = (start + end) / 2;
// 左右の子ノードを再帰的に構築
build(arr, 2 * node + 1, start, mid);
build(arr, 2 * node + 2, mid + 1, end);
// 子ノードをマージ（最大値を保持）
tree[node] = std::max(tree[2 * node + 1], tree[2 * node + 2]);
}
}
// 範囲クエリ（最大値を取得）
long long query(int node, int start, int end, int l, int r) {
if (r < start || end < l) {
// 範囲外の場合（最小値を返す）
return LLONG_MIN;
}
if (l <= start && end <= r) {
// 完全に範囲内の場合
return tree[node];
}
// 範囲が部分的に重なる場合
int mid = (start + end) / 2;
long long leftMax = query(2 * node + 1, start, mid, l, r);
long long rightMax = query(2 * node + 2, mid + 1, end, l, r);
return std::max(leftMax, rightMax); // 最大値を取得
}
// 値の更新
void update(int node, int start, int end, int idx, long long val) {
if (start == end) {
// 葉ノードを更新
tree[node] = val;
} else {
int mid = (start + end) / 2;
if (idx <= mid) {
// 左部分木を更新
update(2 * node + 1, start, mid, idx, val);
} else {
// 右部分木を更新
update(2 * node + 2, mid + 1, end, idx, val);
}
// 親ノードの値を更新（最大値を保持）
tree[node] = std::max(tree[2 * node + 1], tree[2 * node + 2]);
}
}
public:
// コンストラクタ: 配列を受け取り、セグメントツリーを構築
SegmentTreeMax(const std::vector<long long>& arr) {
size = arr.size();
tree.resize(4 * size);
build(arr, 0, 0, size - 1);
}
// 範囲クエリ（最大値）の公開メソッド
long long query(int l, int r) {
return query(0, 0, size - 1, l, r);
}
// 値の更新の公開メソッド
void update(int idx, long long val) {
update(0, 0, size - 1, idx, val);
}
};
class SegmentTreeMin {
private:
std::vector<long long> tree; // セグメントツリー（区間の最小値）
int size; // 配列のサイズ
// セグメントツリーの構築
void build(const std::vector<long long>& arr, int node, int start, int end) {
if (start == end) {
tree[node] = arr[start];
} else {
int mid = (start + end) / 2;
build(arr, 2 * node + 1, start, mid);
build(arr, 2 * node + 2, mid + 1, end);
tree[node] = std::min(tree[2 * node + 1], tree[2 * node + 2]);
}
}
// 範囲クエリ（最小値を取得）
long long query(int node, int start, int end, int l, int r) {
if (r < start || end < l) {
return LLONG_MAX; // 範囲外なら最大値を返す（最小値を取るため）
}
if (l <= start && end <= r) {
return tree[node];
}
int mid = (start + end) / 2;
long long leftMin = query(2 * node + 1, start, mid, l, r);
long long rightMin = query(2 * node + 2, mid + 1, end, l, r);
return std::min(leftMin, rightMin); // 最小値を取得
}
// 値の更新
void update(int node, int start, int end, int idx, long long val) {
if (start == end) {
tree[node] = val;
} else {
int mid = (start + end) / 2;
if (idx <= mid) {
update(2 * node + 1, start, mid, idx, val);
} else {
update(2 * node + 2, mid + 1, end, idx, val);
}
tree[node] = std::min(tree[2 * node + 1], tree[2 * node + 2]);
}
}
public:
SegmentTreeMin(const std::vector<long long>& arr) {
size = arr.size();
tree.resize(4 * size);
build(arr, 0, 0, size - 1);
}
long long query(int l, int r) {
return query(0, 0, size - 1, l, r);
}
void update(int idx, long long val) {
update(0, 0, size - 1, idx, val);
}
};
class LazySegmentTreeSum {
private:
int n; // 配列のサイズ
vector<long long> tree; // セグメントツリーのデータ
vector<long long> lazy; // 遅延評価用のデータ
// 区間の合計を計算する (加算クエリに対応)
void apply(int node, int start, int end, long long value) {
tree[node] += value * (end - start + 1); // ノードの値を更新
if (start != end) { // 子ノードが存在する場合
lazy[node * 2] += value; // 左の子ノードに遅延を追加
lazy[node * 2 + 1] += value; // 右の子ノードに遅延を追加
}
}
// 遅延を伝播する
void propagate(int node, int start, int end) {
if (lazy[node] != 0) { // 遅延が存在する場合
apply(node, start, end, lazy[node]);
lazy[node] = 0; // 遅延をクリア
}
}
// 区間更新 (内部)
void updateRange(int node, int start, int end, int l, int r, long long value) {
propagate(node, start, end); // 遅延を反映
if (start > r || end < l) return; // 完全に範囲外
if (start >= l && end <= r) { // 完全に範囲内
apply(node, start, end, value);
return;
}
// 部分的に範囲内
int mid = (start + end) / 2;
updateRange(node * 2, start, mid, l, r, value);
updateRange(node * 2 + 1, mid + 1, end, l, r, value);
tree[node] = tree[node * 2] + tree[node * 2 + 1]; // 子ノードの結果を合成
}
// 区間クエリ (内部)
long long queryRange(int node, int start, int end, int l, int r) {
propagate(node, start, end); // 遅延を反映
if (start > r || end < l) return 0; // 完全に範囲外
if (start >= l && end <= r) return tree[node]; // 完全に範囲内
// 部分的に範囲内
int mid = (start + end) / 2;
long long left = queryRange(node * 2, start, mid, l, r);
long long right = queryRange(node * 2 + 1, mid + 1, end, l, r);
return left + right; // 子ノードの結果を合成
}
public:
LazySegmentTreeSum(int size) {
n = size;
tree.resize(4 * n, 0); // セグメントツリーのサイズ
lazy.resize(4 * n, 0); // 遅延配列のサイズ
}
// 区間更新
void update(int l, int r, long long value) {
updateRange(1, 0, n - 1, l, r, value);
}
// 区間クエリ
long long query(int l, int r) {
return queryRange(1, 0, n - 1, l, r);
}
};
class LazySegmentTreeMax {
private:
int n; // 配列サイズ
vector<long long> tree; // 区間最大値
vector<long long> lazy; // 遅延加算
// 遅延値をノードに適用
void apply(int node, int start, int end, long long value) {
tree[node] += value; // 最大値に加算
if (start != end) { // 葉でなければ子へ遅延伝播
lazy[node * 2] += value;
lazy[node * 2 + 1] += value;
}
}
// 遅延伝播
void propagate(int node, int start, int end) {
if (lazy[node] != 0) {
apply(node, start, end, lazy[node]);
lazy[node] = 0;
}
}
// 区間更新
void updateRange(int node, int start, int end,
int l, int r, long long value) {
propagate(node, start, end);
if (start > r || end < l) return; // 範囲外
if (start >= l && end <= r) { // 完全包含
apply(node, start, end, value);
return;
}
int mid = (start + end) / 2;
updateRange(node * 2, start, mid, l, r, value);
updateRange(node * 2 + 1, mid + 1, end, l, r, value);
tree[node] = max(tree[node * 2], tree[node * 2 + 1]);
}
// 区間クエリ
long long queryRange(int node, int start, int end,
int l, int r) {
propagate(node, start, end);
if (start > r || end < l) return LLONG_MIN; // 単位元
if (start >= l && end <= r) return tree[node];
int mid = (start + end) / 2;
long long left = queryRange(node * 2, start, mid, l, r);
long long right = queryRange(node * 2 + 1, mid + 1, end, l, r);
return max(left, right);
}
public:
LazySegmentTreeMax(int size) {
n = size;
tree.resize(4 * n, 0);
lazy.resize(4 * n, 0);
}
// 区間加算
void update(int l, int r, long long value) {
updateRange(1, 0, n - 1, l, r, value);
}
// 区間最大値取得
long long query(int l, int r) {
return queryRange(1, 0, n - 1, l, r);
}
};
class LazySegmentTreeMin {
private:
int n; // 配列のサイズ
vector<long long> tree; // 区間最小値を保持
vector<long long> lazy; // 遅延加算を保持
// 遅延を適用
void apply(int node, int start, int end, long long value) {
tree[node] += value; // 区間の最小値を一括加算
if (start != end) { // 葉でなければ子に遅延を伝える
lazy[node * 2] += value;
lazy[node * 2 + 1] += value;
}
}
// 遅延を伝播
void propagate(int node, int start, int end) {
if (lazy[node] != 0) {
apply(node, start, end, lazy[node]);
lazy[node] = 0;
}
}
// 区間更新 (内部)
void updateRange(int node, int start, int end, int l, int r, long long value) {
propagate(node, start, end);
if (start > r || end < l) return; // 範囲外
if (start >= l && end <= r) { // 完全に範囲内
apply(node, start, end, value);
return;
}
int mid = (start + end) / 2;
updateRange(node * 2, start, mid, l, r, value);
updateRange(node * 2 + 1, mid + 1, end, l, r, value);
tree[node] = min(tree[node * 2], tree[node * 2 + 1]);
}
// 区間クエリ (内部)
long long queryRange(int node, int start, int end, int l, int r) {
propagate(node, start, end);
if (start > r || end < l) return LLONG_MAX; // 範囲外は無限大
if (start >= l && end <= r) return tree[node];
int mid = (start + end) / 2;
long long left = queryRange(node * 2, start, mid, l, r);
long long right = queryRange(node * 2 + 1, mid + 1, end, l, r);
return min(left, right);
}
public:
LazySegmentTreeMin(int size) {
n = size;
tree.resize(4 * n, 0); // 区間最小値 (初期値は0で構築)
lazy.resize(4 * n, 0); // 遅延配列
}
// 区間更新
void update(int l, int r, long long value) {
updateRange(1, 0, n - 1, l, r, value);
}
// 区間クエリ
long long query(int l, int r) {
return queryRange(1, 0, n - 1, l, r);
}
};
vector<long long> fact, fact_inv, inv;
/* init_nCk :二項係数のための前処理
計算量:O(n)
*/
void init_nCk(int SIZE) {
fact.resize(SIZE + 5);
fact_inv.resize(SIZE + 5);
inv.resize(SIZE + 5);
fact[0] = fact[1] = 1;
fact_inv[0] = fact_inv[1] = 1;
inv[1] = 1;
for (int i = 2; i < SIZE + 5; i++) {
fact[i] = fact[i - 1] * i % mod;
inv[i] = mod - inv[mod % i] * (mod / i) % mod;
fact_inv[i] = fact_inv[i - 1] * inv[i] % mod;
}
}
/* nCk :modでの二項係数を求める(前処理 int_nCk が必要)
計算量:O(1)
*/
long long nCk(int n, int k) {
if(n < k) return 0;
if(n < 0 || k < 0) return 0;
return fact[n] * (fact_inv[k] * fact_inv[n - k] % mod) % mod;
}
int main()
{
auto[n,m,k] = re.ll3();
auto c = re.array.ll();
vector<vector<pair<ll,ll>>> con(n*(k+1));
for(int i = 0; i < m; i++)
{
auto[u,v] = re.ll2();
u--; v--;
con.at(u).push_back({v,c.at(i)});
con.at(v).push_back({u,c.at(i)});
for(int j = 1; j <= k; j++)
{
con.at(u+n*j).push_back({v+n*j,c.at(i)});
con.at(v+n*j).push_back({u+n*j,c.at(i)});
con.at(u+n*(j-1)).push_back({v+n*j,0});
con.at(v+n*(j-1)).push_back({u+n*j,0});
}
}
priority_queue<pair<ll,ll>> q;
q.push({0,0});
vector<ll> dis(n*(k+1),longMax);
dis.at(0) = 0;
while(q.size())
{
auto[d,i] = q.top();
d *= -1;
q.pop();
if(dis.at(i) < d) continue;
if(i%n == n-1)
{
write(d);
return 0;
}
for(auto[j,w] : con.at(i))
{
if(dis.at(j) > d+w)
{
dis.at(j) = d+w;
q.push({-d-w, j});
}
}
}
writeMinus1();
}