제출 #882182

#제출 시각아이디문제언어결과실행 시간메모리
882182viwlesxqCommuter Pass (JOI18_commuter_pass)C++17
15 / 100
662 ms45972 KiB
// ↘ ⬇ ⬇ ⬇ ⬇ ⬇ ↙ // ➡ IOI, IZhO ⬅ // ↗ ⬆ ⬆ ⬆ ⬆ ⬆ ↖ //⠀⠀⢠⣤⡄⢠⣤⣤⣤⣤⣤⣤⡄⢠⣤⡄⠀⠀⠀⠀⠀⠀⠀⠀ //⠀⠀⢸⣿⡇⢸⣿⣿⣿⣿⣿⣿⡇⢸⣿⡇⠀⠀⠀⠀⠀⠀⠀⠀ //⠀⠀⢸⣿⡇⢸⣿⣿⣿⣿⣿⣿⡇⢸⣿⡇⠀⠀⠀⠀⠀⠀⠀⠀ //⠀⠀⢸⣿⡇⢸⣿⣿⣿⣿⣿⣿⡇⢸⣿⡇⠀⠀⠀⠀⠀⠀⠀⠀ //⠀⠀⢸⣿⡇⢸⣿⣿⣿⣿⣿⣿⡇⢸⣿⡇⠀⠀⠀⠀⠀⠀⠀⠀ //⠀⠀⢸⣿⡇⢸⣿⣿⣿⣿⣿⣿⡇⢸⣿⡇⠀⠀⠀⠀⠀⠀⠀⠀ //⠀⠀⠀⠙⠃⠘⠛⠛⠛⠛⠛⠛⠃⠘⠋⠀⠀⠀⠀⠀⠀⠀⠀⠀ //⠀⠀⠀ ⠘⠛⠛⠛⠛⠛⠛⠛⠛⠃⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀ //⠀⠀⠀⠀⠀⣠⣶⣶⠂⣰⣶⣶⣄⡀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀ //⠀⠀⠀⢀⣾⣿⣿⡏⢠⣿⣿⣿⣿⣿⣆⠀⠀⠀⠀⠀⠀⠀⠀⠀ //⠀⠀⠀⡈⠻⣿⣿⣶⣾⣿⣿⣿⣿⠿⠋⡀⠀⠀⠀⠀⠀⠀⠀⠀ //⠀⠀⠀⣿⣶⣄⠙⣿⣿⣿⣿⣟⢁⣴⣾⡇⠀⠀⠀⠀⠀⠀⠀⠀ //⠀⠀⠀⢹⣿⡏⢠⣿⠟⠛⢿⣿⣿⣿⡿⠁⠀⠀⠀⠀⠀⠀⠀⠀ //⠀⠀⠀⠀⠙⠀⠀⣠⣶⣷⣤⡈⠛⠛⠁⠀⠀⠀⠀⠀⠀⠀⠀⠀ //⠀⠀⠀⠀⠀⠀⠈⠉⠛⠛⠋⠉⠀⠀ #include <bits/stdc++.h> using namespace std; #define int long long #define all(x) x.begin(), x.end() #define size(x) (int)x.size() #define pb push_back #define eb emplace_back template <typename S> bool chmin(S &a, const S b) { if (a > b) { a = b; return true; } return false; } template <typename S> bool chmax(S &a, const S b) { if (a < b) { a = b; return true; } return false; } const int mod = 998244353; const int MOD = 1e9 + 7; const int inf = 1e9 + 7; const int INF = 1e18 + 7; const double eps = 1e-6; const double EPS = 1e-9; const int N = 1e5 + 1; vector<pair<int, int>> g[N]; vector<int> d(N, INF), p(N, -1); map<pair<int, int>, bool> used; void dijkstra(int init) { priority_queue<pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>>> q; q.push({0, init}); d[init] = 0; while (!q.empty()) { int v = q.top().second; q.pop(); for (auto [to, w] : g[v]) { int add = (used[{v, to}] ? 0 : w); if (chmin(d[to], d[v] + add)) { p[to] = v; q.emplace(d[to], to); } } } } signed main() { ios::sync_with_stdio(false); cin.tie(nullptr); int n, m, s, t, u, v; cin >> n >> m; cin >> s >> t; cin >> u >> v; for (int i = 0; i < m; ++i) { int a, b, c; cin >> a >> b >> c; g[a].eb(b, c); g[b].eb(a, c); } dijkstra(s); int x = t; while (p[x] != -1) { used[{p[x], x}] = used[{x, p[x]}] = true; x = p[x]; } fill(all(d), INF); dijkstra(u); cout << d[v]; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...