제출 #1043797

#제출 시각아이디문제언어결과실행 시간메모리
1043797fauzCommuter Pass (JOI18_commuter_pass)C++14
0 / 100
141 ms37512 KiB
#include <bits/stdc++.h> #define fi first #define se second #define int long long using namespace std; const int MAXN = 1001; typedef pair<int, int> II; int n, m, s, t, u, v; long long d[MAXN][MAXN]; vector<II> g[MAXN]; set<II> q; void dijk(int a) { q.insert(II(0, a)); d[a][a] = 0; while (!q.empty()) { int x = q.begin()->se; q.erase(q.begin()); for (II node : g[x]) { int y = node.fi, w = node.se; if (d[a][y] > d[a][x] + w) { if (d[a][y] < LLONG_MAX) q.erase(II(d[a][y], y)); d[a][y] = d[a][x] + w; q.insert(II(d[a][y], y)); } } } } bool clear[MAXN]; int32_t main() { cin >> n >> m >> s >> t >> u >> v; for (int i = 1; i <= m; ++i) { int a, b, c; cin >> a >> b >> c; g[a].push_back(II(b, c)); g[b].push_back(II(a, c)); } for (int i = 1; i <= n; ++i) for (int j = 1; j <= n; ++j) d[i][j] = LLONG_MAX; vector<int> T; T.push_back(t); for (int i = 1; i <= n; ++i) dijk(i); long long ans = LLONG_MAX; for (int i = 1; i <= n; ++i) for (int j = 1; j <= n; ++j) if (d[s][i] + d[i][j] + d[j][t] == d[s][t]) ans = min(ans, d[u][i] + d[j][v]); cout << ans; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...