# TOI練習賽202205潛力組
### [第一題](https://zerojudge.tw/ShowProblem?problemid=q648)
#### 考點：貪心
#### 實作方法
##### 子題一
觀察`n`$\le10$，暴力窮舉每個人是否加入並檢查是否合法。時複雜度度$O({2^n})$
::: spoiler Python 30% code
```python=
from sys import setrecursionlimit
setrecursionlimit(1<<30)
def DFS(level,now):
global ans
if level>=n:
if now and min(now)>=len(now):ans=max(ans,len(now))
return
DFS(level+1,now)
DFS(level+1,now+[nums[level]])
ans=0
n=int(input())
nums=list(map(int,input().split()))
DFS(0,[])
print(ans)
```
:::
::: spoiler C++ 30% code
```cpp=
#include <bits/stdc++.h>
using namespace std;
int ans = 0;
int n;
int nums[200001];
void DFS(int level, vector<int>& now) {
if (level >= n) {
if (!now.empty()) {
int minVal = *min_element(now.begin(), now.end());
if (minVal >= (int)now.size()) {
ans = max(ans, (int)now.size());
}
}
return;
}
DFS(level + 1, now);
now.push_back(nums[level]);
DFS(level + 1, now);
now.pop_back();
}
int main() {
cin >> n;
for (int i = 0; i < n; i++) {cin >> nums[i];}
vector<int> now;
DFS(0, now);
cout << ans << endl;
return 0;
}
```
:::
##### AC
貪心準則：`a[i]`越大的人先加入。
交換論證：假設某個最優解沒有包含一位`a[i]`較大的員工，但包含了一位`a[j]`較小的。
交換 `j`$\rightarrow$`i`：
因為 `a[i]` > `a[j]`，對總人數的限制更寬鬆
所以交換後的新組合會滿足所有限制條件
這樣能產生與原來一樣大小的組合，甚至有可能讓更多人加入
所以：若存在更大 `a[i]` 沒選進來，就一定能優化原解 → 與最優假設矛盾
因此我們貪心選取`a[i]` 較大的員工是正確的。
實作方法：排序`a`(小到大)，從左到右檢查容忍數`a[i]`是否$\ge$人數`n-i`。
時間複雜度$O(n log n +n)$
:::spoiler Python AC(0.3s, 30.3MB) code
```python=
n=int(input())
nums=sorted(list(map(int,input().split())))
for i in range(n):
if nums[i]>=n-i:#現在有n-i個人，目前剛好可以接受，即為答案，越後面答案(n-i)越小
print(n-i)
break
```
:::
::: spoiler C++ AC(0.2s, 1.1MB) code
```cpp=
#include <bits/stdc++.h>
using namespace std;
int main() {
int n;
cin >> n;
vector<int> nums(n);
for (int i = 0; i < n; i++) {cin >> nums[i];}
sort(nums.begin(), nums.end());
for (int i = 0; i < n; i++) {
if (nums[i] >= n - i) {
cout << (n - i) << endl;break;
}
}
return 0;
}
```
:::
### [第二題](https://zerojudge.tw/ShowProblem?problemid=q649)
#### 考點：二分搜、數學
#### 實作方法
##### 子題一
觀察`n`$\le3$，直接判斷答案
`n=1`答案即為$m$
`n=2`答案即為$\lfloor \frac{m}{2} \rfloor$+($m\bmod 2$)
說明：先把每個位置設定成$\lfloor \frac{m}{2} \rfloor$，如果多1個($m\bmod 2$)，答案可增加1，並且$m\ge n$，故不會有`m=1`的問題。
`n=3`
`k=1 or 3`答案即為$\lfloor \frac{m}{3} \rfloor$+$\left[ m\ge4\right]$，$\left[\right]$表[艾佛森括號](https://https://zh.wikipedia.org/zh-tw/%E8%89%BE%E4%BD%9B%E6%A3%AE%E6%8B%AC%E5%8F%B7)
說明：在`m=3`，答案只能是1(因為每個高度必$\ge$ 1)
`m>3`，令`x`為答案，步道可表示為`[x+1,x,x-1]`(1和3是對稱)，明顯得出總和是`3x`，求出`x+1`即為答案。
`k=2`答案即為$\lfloor \frac{m}{3} \rfloor$+$\left[ m\bmod 3 \ge1\right]$，$\left[\right]$表[艾佛森括號](https://https://zh.wikipedia.org/zh-tw/%E8%89%BE%E4%BD%9B%E6%A3%AE%E6%8B%AC%E5%8F%B7)
令`x`為答案，步道可表示為`[x,x,x]`，總和即為`3x`，如果還有剩餘就加上1。
:::spoiler Python 10% code
```python=
for _ in range(int(input())):
ans=0
n,m,k=map(int,input().split())
if n==1:ans=m
elif n==2:ans=m//2+(m%2)
else:
if (k==1 or k==3):ans=m//3+int(m>3)
else:ans=m//3+int(m%3>0)
print(ans)
```
:::
::: spoiler C++ 10% code
```cpp=
#include <bits/stdc++.h>
using namespace std;
int main() {
int t;
cin >> t;
while (t--) {
int n, m, k, ans = 0;
cin >> n >> m >> k;
if (n == 1) ans = m;
else if (n == 2) ans = m / 2 + (m % 2);
else {
if (k == 1 || k == 3) ans = m / 3 + (m > 3 ? 1 : 0);
else ans = m / 3 + (m % 3 > 0 ? 1 : 0);
}
cout << ans << endl;
}
return 0;
}
```
:::
##### 子題二
模擬每次答案增加1的情況，直到`m<0`，輸出答案-1。時間複雜度大約$O(T*\sqrt{m})$
:::spoiler Python 40% code
```python=
for _ in range(int(input())):
n,m,k=map(int,input().split())
ans=1#每個至少為1
m-=n#每個至少為1
l_now=0#儲存左界有幾個數字要增加
r_now=0#儲存右界有幾個數字要增加
while(m>=0):
ans+=1
m-=(1+l_now+r_now)
l_now=min(l_now+1,k-1)
r_now=min(r_now+1,n-k)
print(ans-1)
```
:::
::: spoiler C++ 85% code
```cpp=
#include <bits/stdc++.h>
using namespace std;
int main() {
int t;
cin >> t;
while (t--) {
int n, m, k;
cin >> n >> m >> k;
int ans = 1;//每個至少為1
m -= n;//每個至少為1
int l_now = 0, r_now = 0;//儲存左、右界有幾個數字要增加
while (m >= 0) {
ans += 1;
m -= (1 + l_now + r_now);
l_now = min(l_now + 1, k - 1);
r_now = min(r_now + 1, n - k);
}
cout << ans - 1 << endl;
}
return 0;
}
```
:::
##### AC
預處理每個至少為1，故`m-=n`
用二分搜枚舉答案，檢查總和是否超過`m`
其中左標(小)至少$\ge$$\lfloor \frac{m}{n} \rfloor$，右標(大)最多$m$
計算公式：$((L + mid) * (mid - L + 1) + (mid + R - 1) * (mid - R))$(By [M_SQRT](https://zerojudge.tw/UserStatistic?id=195452)(就是出題者))
時間複雜度$O(T * log m)$
:::spoiler ~~一開始我寫的噁爛判斷~~
```python=
#沒有預處理m-=n
total=now
total+=now*(now-1)
if now-(k-1)<1:total+=abs(k-now)
else:total-=abs(now-k+1)*abs(now-k)//2
if now-(n-k)<1:total+=abs(n-k-now+1)
else:total-=abs(now-(n-k))*abs(now-n+k-1)//2
```
:::
:::spoiler Python 85% code
```python=
def check(X, N, K):
L = max(X - K + 1, 0)
R = max(X - N + K, 0)
return ((L + X) * (X - L + 1) + (X + R - 1) * (X - R)) // 2
def solve():
n,m,k=map(int,input().split())
m-=n
left,right=m//n,m
while(left<=right):
mid=(left+right)//2
if check(mid,n,k)<=m:left=mid+1
else: right=mid-1
print(left)
for _ in range(int(input())):solve()
```
:::
:::spoiler C++ AC(0.5s, 320KB) code
```cpp=
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
ll check(ll X, ll N, ll K) {
ll L = max(X - K + 1, 0LL);
ll R = max(X - N + K, 0LL);
return ((L + X) * (X - L + 1LL) + (X + R - 1LL) * (X - R)) / 2LL;
}
void solve() {
ll n, m, k;
cin >> n >> m >> k;
m -= n;
ll left = m / n, right = m;
while (left <= right) {
ll mid = (left + right) / 2;
if (check(mid, n, k) <= m) left = mid + 1;
else right = mid - 1;
}
cout << left << endl;
}
int main() {
int t;
cin >> t;
while (t--) solve();
return 0;
}
```
:::
##### AC(2)
你以為Python AC無望，~~太天真了~~。
由[M_SQRT](https://zerojudge.tw/UserStatistic?id=195452)大大導出的公式解
下圖是我改過的圖片
`if` 用來判斷哪個步驟開始，`m`不夠繼續。時間複雜度$O(T)$。
:::spoiler Python AC(1s,3.4MB) code
```python=
for _ in range(int(input())):
n,m,k = map(int, input().split())
if k>n//2:k=n-k+1
m-=n
if m<k*k:
print(int(m**0.5)+1)
continue
m-=k*k
temp=(n+2*k)*(n-2*k+1)//2
if m<temp:
print(int(((8 * (k * (2 * k - 1) + m) + 1)**0.5 - 1) / 2) - k + 2)
continue
m -= temp
print(m//n+n-k+2)
```
:::
::: spoiler Python AC(0.4s,7.9MB) code(I/O優化)
```python=
def main():
from sys import stdin,stdout
input=stdin.readline
print=stdout.write
for _ in range(int(input())):
n,m,k = map(int, input().split())
if k>n//2:k=n-k+1
m-=n
if m<k*k:
print(str(int(m**0.5)+1)+"\n")
continue
m-=k*k
temp=(n+2*k)*(n-2*k+1)//2
if m<temp:
print(str(int(((8 * (k * (2 * k - 1) + m) + 1)**0.5 - 1) / 2) - k + 2)+"\n")
continue
m -= temp
print(str(m//n+n-k+2)+"\n")
main()
```
:::
::: spoiler C++ AC(0.5s, 328KB) code
```cpp=
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
int main() {
int t;
cin >> t;
while (t--) {
ll n, m, k;
cin >> n >> m >> k;
if (k > n / 2) k = n - k + 1;
m -= n;
if (m < k * k) {
cout << (ll)(sqrt(m) + 1) << endl;
continue;
}
m -= k * k;
ll temp = (n + 2 * k) * (n - 2 * k + 1) / 2;
if (m < temp) {
ll val = (8 * (k * (2 * k - 1) + m) + 1);
cout << (ll)((sqrt(val) - 1) / 2) - k + 2 << endl;
continue;
}
m -= temp;
cout << m / n + n - k + 2 << endl;
}
return 0;
}
```
:::
::: spoiler C++ AC(88ms, 356KB) code(I/O優化)
```cpp=
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
int main() {
ios::sync_with_stdio(false);
cin.tie(0);
int t;
cin >> t;
while (t--) {
ll n, m, k;
cin >> n >> m >> k;
if (k > n / 2) k = n - k + 1;
m -= n;
if (m < k * k) {
cout << (ll)(sqrt(m) + 1) << '\n';
continue;
}
m -= k * k;
ll temp = (n + 2 * k) * (n - 2 * k + 1) / 2;
if (m < temp) {
ll val = 8 * (k * (2 * k - 1) + m) + 1;
cout << (ll)((sqrt(val) - 1) / 2) - k + 2 << '\n';
continue;
}
m -= temp;
cout << m / n + n - k + 2 << '\n';
}
return 0;
}
```
:::
::: spoiler C++ AC(62ms, 336KB) code(scanf,printf)
```cpp=
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
int main() {
int t;
scanf("%d", &t);
while (t--) {
ll n, m, k;
scanf("%lld %lld %lld", &n, &m, &k);
if (k > n / 2) k = n - k + 1;
m -= n;
if (m < k * k) {
printf("%lld\n", (ll)(sqrt(m) + 1));
continue;
}
m -= k * k;
ll temp = (n + 2 * k) * (n - 2 * k + 1) / 2;
if (m < temp) {
ll val = 8 * (k * (2 * k - 1) + m) + 1;
printf("%lld\n", (ll)((sqrt(val) - 1) / 2) - k + 2);
continue;
}
m -= temp;
printf("%lld\n", m / n + n - k + 2);
}
return 0;
}
```
:::
### [第三題](https://zerojudge.tw/ShowProblem?problemid=q650)
#### 考點：Dijkstra
#### 實作方法
##### 子題一
觀察`n`$\le10$，暴力BFS
::: spoiler Python 35% code
```python=
import sys
from collections import deque
def min_refuel_wait_time_sub1(N, M, F, wait_times, roads):
graph = [[] for _ in range(N+1)]
for a,b,c in roads:
graph[a].append((b,c))
graph[b].append((a,c))
# dist[city][fuel] = 最少等待時間
dist = [[float('inf')] * (F+1) for _ in range(N+1)]
dist[1][F] = 0
queue = deque()
queue.append((1, F))
while queue:
city, fuel = queue.popleft()
curr_wait = dist[city][fuel]
if city == N:
return curr_wait
# 在城市加油（如果不是起點或終點）
if city != 1 and city != N:
new_wait = curr_wait + wait_times[city]
if dist[city][F] > new_wait:
dist[city][F] = new_wait
queue.append((city, F))
# 走鄰居，消耗油量
for nxt, cost in graph[city]:
if fuel >= cost:
nfuel = fuel - cost
if dist[nxt][nfuel] > curr_wait:
dist[nxt][nfuel] = curr_wait
queue.append((nxt, nfuel))
return -1
def main():
input = sys.stdin.read
data = input().split()
idx=0
N = int(data[idx]); idx+=1
M = int(data[idx]); idx+=1
F = int(data[idx]); idx+=1
wait_input = list(map(int, data[idx:idx+N-2]))
idx += N-2
wait_times = [0]*(N+1)
for i in range(2, N):
wait_times[i] = wait_input[i-2]
roads = []
for _ in range(M):
a,b,c = int(data[idx]), int(data[idx+1]), int(data[idx+2])
idx+=3
roads.append((a,b,c))
ans = min_refuel_wait_time_sub1(N,M,F,wait_times,roads)
print(ans)
if __name__ == "__main__":
main()
```
:::
:::spoiler C++ 40% code
```cpp=
#include <bits/stdc++.h>
using namespace std;
int min_refuel_wait_time_sub1(int N, int M, int F, vector<int>& wait_times, vector<tuple<int,int,int>>& roads) {
vector<vector<pair<int,int>>> graph(N+1);
for (auto& e : roads) {
int a,b,c; tie(a,b,c) = e;
graph[a].emplace_back(b,c);
graph[b].emplace_back(a,c);
}
vector<vector<int>> dist(N+1, vector<int>(F+1, INT_MAX));
dist[1][F] = 0;
deque<pair<int,int>> queue;
queue.emplace_back(1, F);
while (!queue.empty()) {
auto [city, fuel] = queue.front();
queue.pop_front();
int curr_wait = dist[city][fuel];
if (city == N) return curr_wait;
if (city != 1 && city != N) {
int new_wait = curr_wait + wait_times[city];
if (dist[city][F] > new_wait) {
dist[city][F] = new_wait;
queue.emplace_back(city, F);
}
}
for (auto& [nxt, cost] : graph[city]) {
if (fuel >= cost) {
int nfuel = fuel - cost;
if (dist[nxt][nfuel] > curr_wait) {
dist[nxt][nfuel] = curr_wait;
queue.emplace_back(nxt, nfuel);
}
}
}
}
return -1;
}
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
int N, M, F;
cin >> N >> M >> F;
vector<int> wait_times(N+1, 0);
for (int i = 2; i <= N-1; i++) {
cin >> wait_times[i];
}
vector<tuple<int,int,int>> roads(M);
for (int i = 0; i < M; i++) {
int a,b,c;
cin >> a >> b >> c;
roads[i] = make_tuple(a,b,c);
}
cout << min_refuel_wait_time_sub1(N, M, F, wait_times, roads) << "\n";
return 0;
}
```
:::
##### 子題二
簡化等待時間加權 Dijkstra(只算加油次數)
:::spoiler Python 35% code
```python=
import sys
import heapq
from collections import defaultdict
def min_refuel_wait_time_sub2(N, M, F, wait_times, roads):
# 所有ti=1時，可以將等待時間當成加油次數 (等價於1)
graph = defaultdict(list)
for a,b,c in roads:
graph[a].append((b,c))
graph[b].append((a,c))
def dijkstra_from(city):
dist = [float('inf')] * (N+1)
dist[city] = 0
pq = [(0, city)]
reachable = []
while pq:
d,u = heapq.heappop(pq)
if d > F:
continue
reachable.append((u,d))
for v,w in graph[u]:
nd = d + w
if nd <= F and nd < dist[v]:
dist[v] = nd
heapq.heappush(pq,(nd,v))
return reachable
min_wait = [float('inf')] * (N+1)
min_wait[1] = 0
pq = [(0,1)]
while pq:
curr_wait, city = heapq.heappop(pq)
if city == N:
return curr_wait
if curr_wait > min_wait[city]:
continue
for next_city, dist in dijkstra_from(city):
if next_city == city:
continue
# ti = 1 for all i
wtime = 1 if next_city != 1 and next_city != N else 0
new_wait = curr_wait + wtime
if new_wait < min_wait[next_city]:
min_wait[next_city] = new_wait
heapq.heappush(pq, (new_wait, next_city))
return -1
def main():
input=sys.stdin.read
data = input().split()
idx=0
N = int(data[idx]); idx+=1
M = int(data[idx]); idx+=1
F = int(data[idx]); idx+=1
wait_input = list(map(int, data[idx:idx+N-2]))
idx += N-2
wait_times = [0]*(N+1)
for i in range(2, N):
wait_times[i] = wait_input[i-2]
roads = []
for _ in range(M):
a,b,c = int(data[idx]), int(data[idx+1]), int(data[idx+2])
idx+=3
roads.append((a,b,c))
ans = min_refuel_wait_time_sub2(N,M,F,wait_times,roads)
print(ans)
if __name__ == "__main__":
main()
```
:::
::: spoiler C++ 35% code
```cpp=
#include <bits/stdc++.h>
using namespace std;
int min_refuel_wait_time_sub2(int N, int M, int F, vector<int>& wait_times, vector<tuple<int,int,int>>& roads) {
vector<vector<pair<int,int>>> graph(N+1);
for (auto& e : roads) {
int a,b,c; tie(a,b,c) = e;
graph[a].emplace_back(b,c);
graph[b].emplace_back(a,c);
}
auto dijkstra_from = [&](int city) {
vector<int> dist(N+1, INT_MAX);
dist[city] = 0;
priority_queue<pair<int,int>, vector<pair<int,int>>, greater<>> pq;
pq.emplace(0, city);
vector<pair<int,int>> reachable;
while (!pq.empty()) {
auto [d,u] = pq.top(); pq.pop();
if (d > F) continue;
reachable.emplace_back(u,d);
for (auto& [v,w] : graph[u]) {
int nd = d + w;
if (nd <= F && nd < dist[v]) {
dist[v] = nd;
pq.emplace(nd, v);
}
}
}
return reachable;
};
vector<int> min_wait(N+1, INT_MAX);
min_wait[1] = 0;
priority_queue<pair<int,int>, vector<pair<int,int>>, greater<>> pq;
pq.emplace(0, 1);
while (!pq.empty()) {
auto [curr_wait, city] = pq.top(); pq.pop();
if (city == N) return curr_wait;
if (curr_wait > min_wait[city]) continue;
for (auto& [next_city, dist] : dijkstra_from(city)) {
if (next_city == city) continue;
int wtime = (next_city != 1 && next_city != N) ? 1 : 0;
int new_wait = curr_wait + wtime;
if (new_wait < min_wait[next_city]) {
min_wait[next_city] = new_wait;
pq.emplace(new_wait, next_city);
}
}
}
return -1;
}
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
int N, M, F;
cin >> N >> M >> F;
vector<int> wait_times(N+1, 0);
for (int i = 2; i <= N-1; i++) {
cin >> wait_times[i];
}
vector<tuple<int,int,int>> roads(M);
for (int i = 0; i < M; i++) {
int a,b,c;
cin >> a >> b >> c;
roads[i] = make_tuple(a,b,c);
}
cout << min_refuel_wait_time_sub2(N, M, F, wait_times, roads) << "\n";
return 0;
}
```
:::
##### AC
用同樣暴力加油Dijkstra，考慮不同等待時間
::: spoiler Python AC(2.4s, 11.2MB) code
``` python=
import sys
import heapq
from collections import defaultdict
def min_refuel_wait_time_full(N, M, F, wait_times, roads):
graph = defaultdict(list)
for a,b,c in roads:
graph[a].append((b,c))
graph[b].append((a,c))
def dijkstra_from(city):
dist = [float('inf')] * (N+1)
dist[city] = 0
pq = [(0, city)]
reachable = []
while pq:
d,u = heapq.heappop(pq)
if d > F:
continue
reachable.append((u,d))
for v,w in graph[u]:
nd = d + w
if nd <= F and nd < dist[v]:
dist[v] = nd
heapq.heappush(pq,(nd,v))
return reachable
min_wait = [float('inf')] * (N+1)
min_wait[1] = 0
pq = [(0,1)]
while pq:
curr_wait, city = heapq.heappop(pq)
if city == N:
return curr_wait
if curr_wait > min_wait[city]:
continue
for next_city, dist in dijkstra_from(city):
if next_city == city:
continue
wtime = wait_times[next_city]
new_wait = curr_wait + wtime
if new_wait < min_wait[next_city]:
min_wait[next_city] = new_wait
heapq.heappush(pq, (new_wait, next_city))
return -1
def main():
input=sys.stdin.read
data = input().split()
idx=0
N = int(data[idx]); idx+=1
M = int(data[idx]); idx+=1
F = int(data[idx]); idx+=1
wait_input = list(map(int, data[idx:idx+N-2]))
idx += N-2
wait_times = [0]*(N+1)
for i in range(2, N):
wait_times[i] = wait_input[i-2]
roads = []
for _ in range(M):
a,b,c = int(data[idx]), int(data[idx+1]), int(data[idx+2])
idx+=3
roads.append((a,b,c))
ans = min_refuel_wait_time_full(N,M,F,wait_times,roads)
print(ans)
if __name__ == "__main__":
main()
```
:::
::: spoiler C++ AC(20ms, 1.1MB) code
```cpp=
#include <bits/stdc++.h>
using namespace std;
int min_refuel_wait_time_full(int N, int M, int F, vector<int>& wait_times, vector<tuple<int,int,int>>& roads) {
vector<vector<pair<int,int>>> graph(N+1);
for (auto& e : roads) {
int a,b,c; tie(a,b,c) = e;
graph[a].emplace_back(b,c);
graph[b].emplace_back(a,c);
}
auto dijkstra_from = [&](int city) {
vector<int> dist(N+1, INT_MAX);
dist[city] = 0;
priority_queue<pair<int,int>, vector<pair<int,int>>, greater<>> pq;
pq.emplace(0, city);
vector<pair<int,int>> reachable;
while (!pq.empty()) {
auto [d,u] = pq.top(); pq.pop();
if (d > F) continue;
reachable.emplace_back(u,d);
for (auto& [v,w] : graph[u]) {
int nd = d + w;
if (nd <= F && nd < dist[v]) {
dist[v] = nd;
pq.emplace(nd, v);
}
}
}
return reachable;
};
vector<int> min_wait(N+1, INT_MAX);
min_wait[1] = 0;
priority_queue<pair<int,int>, vector<pair<int,int>>, greater<>> pq;
pq.emplace(0, 1);
while (!pq.empty()) {
auto [curr_wait, city] = pq.top(); pq.pop();
if (city == N) return curr_wait;
if (curr_wait > min_wait[city]) continue;
for (auto& [next_city, dist] : dijkstra_from(city)) {
if (next_city == city) continue;
int wtime = wait_times[next_city];
int new_wait = curr_wait + wtime;
if (new_wait < min_wait[next_city]) {
min_wait[next_city] = new_wait;
pq.emplace(new_wait, next_city);
}
}
}
return -1;
}
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
int N, M, F;
cin >> N >> M >> F;
vector<int> wait_times(N+1, 0);
for (int i = 2; i <= N-1; i++) {
cin >> wait_times[i];
}
vector<tuple<int,int,int>> roads(M);
for (int i = 0; i < M; i++) {
int a,b,c;
cin >> a >> b >> c;
roads[i] = make_tuple(a,b,c);
}
cout << min_refuel_wait_time_full(N, M, F, wait_times, roads) << "\n";
return 0;
}
```
:::
Sign in with Wallet
Connect another wallet