Submission #1087635

#TimeUsernameProblemLanguageResultExecution timeMemory
1087635FubuGoldCommuter Pass (JOI18_commuter_pass)C++14
0 / 100
2070 ms234420 KiB
#include<bits/stdc++.h> #define int long long #define pii pair<int,int> using namespace std; const int maxn = 1e5 + 2; const int inf = LLONG_MAX / 5; int n,m,ans=inf; int D,S,T,U,V; vector<pii> a[maxn]; vector<int> b[maxn]; int d[5][maxn], tq[maxn], tu[maxn], tv[maxn]; multiset<int> su,sv; void BRUTE(int u, int cnt) { for (int i = 1; i <= n; i++) d[cnt][i] = inf; d[cnt][u] = 0; for (int i = 1; i <= n; i++) { for (int u = 1; u <= n; u++) { for (pii tmp: a[u]) { int v,val; tie(v,val) = tmp; d[cnt][v] = min(d[cnt][v], d[cnt][u] + val); } } } } void dfs(int u) { su.insert(d[2][u]); sv.insert(d[3][u]); // cerr << "> "<< u << " " << T << endl; if (u == T) { ans = min(ans, *su.begin()+ *sv.begin()); return; } for (pii tmp : a[u]) { int v = tmp.first; // cerr << "? " << v << " and " << D << endl; if ( d[0][u] + tmp.second + d[1][v] == D ) { dfs(v); } } su.erase(su.find(d[2][u])); sv.erase(sv.find(d[3][u])); } signed main() { // freopen("BUS.INP", "r", stdin); // freopen("BUS.ANS", "w", stdout); cin.tie(0) -> sync_with_stdio(0); cin >> n >> m; cin >> S >> T >> U >> V; for (int i= 1; i <= m; i++) { int x,y,h; cin >> x >> y >> h; a[x].push_back({y,h}); a[y].push_back({x,h}); } BRUTE(S,0); BRUTE(T,1); BRUTE(U,2); BRUTE(V,3); D = d[0][T]; // for (int i= 1; i <= n; i++) cerr << S << " dis: " << i << " = " << d[0][i] << endl; dfs(S); 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...