제출 #931740

#제출 시각아이디문제언어결과실행 시간메모리
931740sofijavelkovskaCommuter Pass (JOI18_commuter_pass)C++17
100 / 100
267 ms25240 KiB
#include <bits/stdc++.h> using namespace std; const int MAXN=100001; const long long INF=1e16; int n, m, s, t, u, v; vector<pair<int, int> > adj[MAXN]; vector<int> shortadj[MAXN]; long long mincost=INF; long long mindist[MAXN]; void dijkstra(int root, long long dist[]) { for (int i=1; i<=n; i++) dist[i]=INF; dist[root]=0; bool visited[n+1]={false}; priority_queue<pair<long long, int> > pq; pq.push({0, root}); while (!pq.empty()) { int x=pq.top().second; pq.pop(); if (visited[x]) continue; visited[x]=true; for (auto edge : adj[x]) { int y=edge.first; int w=edge.second; if (dist[x]+w<dist[y]) { dist[y]=dist[x]+w; pq.push({-dist[y], y}); } } } return; } long long findmin(int x, long long dist1[], long long dist2[]) { if (mindist[x]!=-1) return mindist[x]; mindist[x]=dist1[x]; for (auto y : shortadj[x]) mindist[x]=min(mindist[x], findmin(y, dist1, dist2)); mincost=min(mincost, mindist[x]+dist2[x]); return mindist[x]; } int main() { ios_base::sync_with_stdio(0); cin.tie(0); cin >> n >> m; cin >> s >> t >> u >> v; long long sdist[n+1], tdist[n+1], udist[n+1], vdist[n+1]; for (int i=0; i<m; i++) { int x, y, w; cin >> x >> y >> w; adj[x].push_back({y, w}); adj[y].push_back({x, w}); } dijkstra(s, sdist); dijkstra(t, tdist); dijkstra(u, udist); dijkstra(v, vdist); queue<int> q; q.push(s); bool visited[n+1]={false}; while (!q.empty()) { int x=q.front(); q.pop(); if (visited[x]) continue; visited[x]=true; for (auto edge : adj[x]) { int y=edge.first; int w=edge.second; if (sdist[x]+w>sdist[y]) continue; if (sdist[y]+tdist[y]!=sdist[t]) continue; shortadj[x].push_back(y); q.push(y); } } for (int i=1; i<=n; i++) mindist[i]=-1; findmin(s, udist, vdist); for (int i=1; i<=n; i++) mindist[i]=-1; findmin(s, vdist, udist); mincost=min(mincost, udist[v]); cout << mincost; 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...