Submission #654304

#	TimeUTC-0	Username	Problem	Language	Result	Execution time	Memory
654304	2022-10-30 23:03:36	lunchbox1	Commuter Pass (JOI18_commuter_pass)	C++17	100 / 100	534 ms	22648 KiB

commuter_pass

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
/*
 Commuter Pass
 https://oj.uz/problem/view/JOI18_commuter_pass
*/
#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
template<class T>
using min_pq = priority_queue<T, vector<T>, greater<T>>;
const int N = 1e5;
const LL INF = 1e18;
int main() {
 ios::sync_with_stdio(0), cin.tie(0);
 int n, m; cin >> n >> m;
 int s, t, u, v; cin >> s >> t >> u >> v, s--, t--, u--, v--;
 static vector<pair<int, int>> g[N];
 while (m--) {
  int i, j, c; cin >> i >> j >> c, i--, j--;
  g[i].push_back({j, c}), g[j].push_back({i, c});
 }
 auto gen = [&](int s, LL *dt) {
  min_pq<pair<LL, int>> q;
  fill(dt, dt + n, INF);
  q.push({dt[s] = 0, s});
  while (!q.empty()) {
   auto [d, i] = q.top(); q.pop();
 
 
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX

• Subtask 1: 16 / 16
• Subtask 2: 15 / 15
• Subtask 3: 24 / 24
• Subtask 4: 45 / 45