제출 #700183

#제출 시각아이디문제언어결과실행 시간메모리
700183berrCommuter Pass (JOI18_commuter_pass)C++17
100 / 100
408 ms36080 KiB
// 1 #include <bits/stdc++.h> using namespace std; #define int long long const int N = 1e5+37; vector<array<int, 2>> adj[N]; vector<int> ds, dt, dv, du, adj2[N]; vector<array<int, 2>> a1(N), a2(N); vector<int> d(int x){ vector<int> dist(N, 1e18); dist[x] = 0; priority_queue<array<int, 2>> q; q.push({0, x}); while (q.size()){ int u = -q.top()[0], v = q.top()[1]; q.pop(); for (auto i: adj[v]){ if(dist[i[0]] > u+i[1]){ dist[i[0]] = u + i[1]; q.push({-dist[i[0]], i[0]}); } } } return dist; } signed main(){ ios_base::sync_with_stdio(false); cin.tie(0); int n, m; cin >> n >> m; int s, t, u, v; cin >> s >> t >> u >> v; s--; t--; u--; v--; vector<array<int, 3>> e; for (int i = 0; i < m; i++){ int x, y, z; cin >> x >> y >> z; x--; y--; adj[x].push_back({y, z}); adj[y].push_back({x, z}); e.push_back({x, y, z}); } ds=d(s), dt=d(t), du=d(u), dv=d(v); for (auto i: e){ if(i[2] + ds[i[0]] + dt[i[1]] == ds[t]) adj2[i[0]].push_back(i[1]), adj2[i[1]].push_back(i[0]); if(i[2] + ds[i[1]] + dt[i[0]] == ds[t]) adj2[i[0]].push_back(i[1]), adj2[i[1]].push_back(i[0]); } int a=1e18; for (int i = 0; i < n; i++){ a1[i] = {a, a}; a2[i] = {a, a}; } queue<int> q; q.push(s); vector<int> vis(n); vis[s]=1; while (q.size()){ int c=q.front(); q.pop(); a1[c][0] = min(a1[c][0], dv[c]); a1[c][1] = min(a1[c][1], du[c]); for (auto i: adj2[c]){ if(ds[i] > ds[c]){ a1[i][0] = min(a1[i][0], a1[c][0]); a1[i][1] = min(a1[i][1], a1[c][1]); if(vis[i]==0) q.push(i), vis[i]=1; } } } q.push(t); for(int i=0; i<n; i++) vis[i]=0; vis[t]=1; while (q.size()){ int c=q.front(); q.pop(); a2[c][0] = min(a2[c][0], dv[c]); a2[c][1] = min(a2[c][1], du[c]); for (auto i: adj2[c]){ if(dt[i] > dt[c]){ a2[i][0] = min(a2[i][0], a2[c][0]); a2[i][1] = min(a2[i][1], a2[c][1]); if(vis[i]==0) q.push(i), vis[i]=1; } } } int ans=dv[u]; for(int i=0; i<n; i++){ ans = min({a1[i][0] + a2[i][1], a1[i][1] + a2[i][0], ans}); } 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...