제출 #1113375

#제출 시각아이디문제언어결과실행 시간메모리
1113375Dan4LifeCommuter Pass (JOI18_commuter_pass)C++17
24 / 100
50 ms4680 KiB
#include <bits/stdc++.h> using namespace std; #define pb push_back #define sz(a) (int)a.size() #define all(a) begin(a),end(a) using vi = vector<int>; using ll = long long; using ar2 = array<ll,2>; const int N = (int)3e2+10; const int INF = (int)1e9; const ll LINF = (ll)2e18; int n, m, S, T, U, V; ll dis[N][N]; vector<ar2> adj[N]; void dijkstra(int s, int t){ priority_queue<ar2,vector<ar2>,greater<ar2>> pq; while(sz(pq)) pq.pop(); for(int i = 1; i <= n; i++) dis[t][i]=LINF; dis[t][s] = 0; pq.push({0,s}); while(sz(pq)){ auto [D,a] = pq.top(); pq.pop(); if(D!=dis[t][a]) continue; for(auto [b,w] : adj[a]){ if(dis[t][a]+w<dis[t][b]){ dis[t][b] = dis[t][a]+w; pq.push({dis[t][b],b}); } } } } int main(){ ios_base::sync_with_stdio(false); cin.tie(0); cin >> n >> m >> S >> T >> U >> V; for(int i = 0; i < m; i++){ int a, b, c; cin >> a >> b >> c; adj[a].pb({b,c}), adj[b].pb({a,c}); } for(int i = 1; i <= n; i++) dijkstra(i,i); ll ans = dis[U][V]; for(int i = 1; i <= n; i++){ for(int j = 1; j <= n; j++){ if(dis[S][i]+dis[i][j]+dis[j][T]==dis[S][T]) ans = min({ans, dis[U][i]+dis[j][V], dis[U][j]+dis[i][V]}); } } cout << ans << "\n"; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...