제출 #1203685

#제출 시각아이디문제언어결과실행 시간메모리
1203685andrejikusCommuter Pass (JOI18_commuter_pass)C++20
24 / 100
27 ms2376 KiB
#include <bits/stdc++.h> using namespace std; typedef long long ll; void DBG() { cerr << "]" << endl; } template<class H, class... T> void DBG(H h, T... t) { cerr << to_string(h); if(sizeof...(t)) cerr << ", "; DBG(t...); } #define dbg(...) cerr << "[" << #__VA_ARGS__ << "]: [", DBG(__VA_ARGS__) const int N = 303; const ll inf = 1e18; vector<pair<int, int>> adj[N]; ll d[N][N]; void solve() { int n, m; cin >> n >> m; int s, t; cin >> s >> t; int u, v; cin >> u >> v; for (int i = 1; i <= n; i++) for (int j = 1; j <= n; j++) if (i != j) d[i][j] = inf; for (int i = 0; i < m; i++) { int u, v, c; cin >> u >> v >> c; adj[u].push_back({v, c}); adj[v].push_back({u, c}); d[u][v] = c; d[v][u] = c; } for (int k = 1; k <= n; k++) { for (int i = 1; i <= n; i++) { for (int j = 1; j <= n; j++) { d[i][j] = min(d[i][j], d[i][k] + d[k][j]); } } } ll ans = d[u][v]; for (int i = 1; i <= n; i++) { for (int j = i-1; j >= 1; j--) { if (d[s][j] + d[j][i] + d[i][t] != d[s][t] && d[s][i] + d[i][j] + d[j][t] != d[s][t]) continue; ans = min(ans, d[u][i] + d[j][v]); ans = min(ans, d[u][j] + d[i][v]); } } cout << ans << "\n"; } signed main() { ios::sync_with_stdio(false); cin.tie(0); int t=1; //cin >> t; while (t--) { solve(); } }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...