제출 #1087569

#제출 시각아이디문제언어결과실행 시간메모리
1087569pqthangvCommuter Pass (JOI18_commuter_pass)C++11
15 / 100
2050 ms26568 KiB
#include <bits/stdc++.h> using namespace std; typedef long long ll; const int INF = 1e9 + 5; const ll oo = 1e18 + 5; const int MAXN = 1e5 + 5; #define int ll int n, m, s, t, u, v, dist[MAXN][3], best[MAXN][2]; priority_queue<pair<int, int>, vector<pair<int, int>>, greater<pair<int, int> > > pq; vector<pair<int, int>> adj[MAXN]; int ans; void DJ(int source, int type) { pq.push({0, source}); dist[source][type] = 0; while (!pq.empty()) { pair<int, int> t = pq.top(); pq.pop(); int u = t.second, kcu = t.first; if (kcu > dist[u][type]) continue; for (int i = 0; i < int(adj[u].size()); ++i) { int v = adj[u][i].first, kcv = adj[u][i].second; if (dist[v][type] > dist[u][type] + kcv) { dist[v][type] = dist[u][type] + kcv; pq.push({dist[v][type], v}); } } } } void DFS(int u) { best[u][0] = dist[u][1]; best[u][1] = dist[u][2]; // cout << u << ' '; for (int i = 0; i < int(adj[u].size()); ++i){ int v = adj[u][i].first, kcv = adj[u][i].second; if (dist[v][0] == dist[u][0] - kcv) { DFS(v); best[u][0] = min(best[u][0], best[v][0]); best[u][1] = min(best[u][1], best[v][1]); } } ans = min(ans, dist[u][1] + best[u][1]); ans = min(ans, dist[u][2] + best[u][0]); } void solve() { cin >> n >> m >> s >> t >> u >> v; for (int i = 1; i <= m; ++i) { int u, v, w; cin >> u >> v >> w; adj[u].push_back({v, w}); adj[v].push_back({u, w}); } memset(dist, 0x3f, sizeof(dist)); DJ(s, 0); DJ(u, 1); DJ(v, 2); ans = dist[v][1]; DFS(t); // // cout << dist[3][0] << ' '; // cout << ans; } signed main() { ios_base::sync_with_stdio(0); cin.tie(NULL); cout.tie(NULL); // int T = 1; cin >> T; while(T--) solve(); return 0; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...