oj.uz

답안 #494711

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
494711 2021-12-16T03:14:22 Z keertan Commuter Pass (JOI18_commuter_pass) C++17
100 / 100
 399 ms 35728 KB 
#include<bits/stdc++.h>
using namespace std;
#define int  int64_t
#define all(x) x.begin(),x.end()
#define all1(x) x.rbegin(),x.rend()
#define sz(x) (int)(x.size())
const int N=1e5+5,N1=1e18,mod=1e9+7;
template<class T> using min_heap=priority_queue<T,vector<T>,greater<T>>;
vector<int> adj1[N],adj2[N],adj3[N],disv(N,N1);
int memo[N];
int dp(int u){
  if (memo[u]!=-1){return memo[u];}
  int best=disv[u];
  for (int it:adj1[u]){
    best=min(best,dp(it));
  }
  return memo[u]=best;
}
int memo1[N];
int dpback(int u){
  if (memo1[u]!=-1){return memo1[u];}
  int best=disv[u];
  for (int it:adj2[u]){
    best=min(best,dpback(it));
  }
  return memo1[u]=best;
}
void solve(){
  int n,m,s,t,u,v;
  cin>>n>>m>>s>>t>>u>>v;
  using gh=pair<int,int>;
  vector<gh> adj[n+1];
  for (int i=1,x,y,w;i<=m;i++){
    cin>>x>>y>>w;
    adj[x].emplace_back(y,w);
    adj[y].emplace_back(x,w);
  }
  vector<int> disu(n+1,N1);
  min_heap<pair<int,int>> q;
  q.emplace(0,u);
  disu[u]=0;
  while(!q.empty()){
    int nd,dis;
    tie(dis,nd)=q.top();
    q.pop();
    for (const pair<int,int> &it:adj[nd]){
      if (disu[it.first]>disu[nd]+it.second){
        disu[it.first]=disu[nd]+it.second;
        q.emplace(disu[it.first],it.first);
      }
    }
  }
  disv[v]=0;
  q.emplace(0,v);
  while(!q.empty()){
    int nd,dis;
    tie(dis,nd)=q.top();
    q.pop();
    for (const pair<int,int> &it:adj[nd]){
      if (disv[it.first]>disv[nd]+it.second){
        disv[it.first]=disv[nd]+it.second;
        q.emplace(disv[it.first],it.first);
      }
    }
  }

  vector<int> curdis(n+1,N1);
  curdis[s]=0;
  q.emplace(0,s);
  while(!q.empty()){
    int nd,dis;
    tie(dis,nd)=q.top();
    q.pop();
   
    for (const pair<int,int> &it:adj[nd]){
      if (curdis[it.first]>curdis[nd]+it.second){
        curdis[it.first]=curdis[nd]+it.second;
        adj1[it.first].clear();
        adj1[it.first].emplace_back(nd);
        q.emplace(curdis[it.first],it.first);
      }
      else if (curdis[it.first]==curdis[nd]+it.second){
        adj1[it.first].emplace_back(nd);
      }
    }
  }
   vector<bool> curvis(n+1);

 
  queue<int> q1;
  q1.emplace(t);
  while(!q1.empty()){
    int nd=q1.front();
    q1.pop();
    if (!curvis[nd]){
      curvis[nd]=1;
      for (int it:adj1[nd]){
        adj2[it].emplace_back(nd);
        q1.emplace(it);
      }
    }
  }
  
  
  
  
  
  memset(memo,-1,sizeof(memo));
  memset(memo1,-1,sizeof(memo1));

  int ans=disu[v];
  for (int i=1;i<=n;i++){
    if (!curvis[i]){continue;}
    ans=min(ans,disu[i]+min(dp(i),dpback(i)));
  }
  cout<<ans;
}
int32_t main(){
  ios::sync_with_stdio(false);cin.tie(nullptr);cout.tie(nullptr);
  int tq=1;
  //cin>>tq;
  for (;tq;tq--){solve();}
}

Subtask #1
16.0 / 16.0

# 결과 실행 시간 메모리 Grader output
1 Correct 261 ms 31492 KB Output is correct
2 Correct 339 ms 32312 KB Output is correct
3 Correct 359 ms 34616 KB Output is correct
4 Correct 280 ms 31932 KB Output is correct
5 Correct 322 ms 32824 KB Output is correct
6 Correct 310 ms 31544 KB Output is correct
7 Correct 317 ms 33220 KB Output is correct
8 Correct 328 ms 33080 KB Output is correct
9 Correct 287 ms 31532 KB Output is correct
10 Correct 245 ms 31436 KB Output is correct
11 Correct 113 ms 26760 KB Output is correct
12 Correct 278 ms 31704 KB Output is correct

Subtask #2
15.0 / 15.0

# 결과 실행 시간 메모리 Grader output
1 Correct 324 ms 33524 KB Output is correct
2 Correct 376 ms 33328 KB Output is correct
3 Correct 373 ms 33196 KB Output is correct
4 Correct 368 ms 33524 KB Output is correct
5 Correct 356 ms 33648 KB Output is correct
6 Correct 309 ms 35048 KB Output is correct
7 Correct 347 ms 35728 KB Output is correct
8 Correct 311 ms 32988 KB Output is correct
9 Correct 308 ms 33512 KB Output is correct
10 Correct 320 ms 33244 KB Output is correct
11 Correct 139 ms 28228 KB Output is correct
12 Correct 292 ms 34848 KB Output is correct

Subtask #3
24.0 / 24.0

# 결과 실행 시간 메모리 Grader output
1 Correct 14 ms 11564 KB Output is correct
2 Correct 5 ms 9676 KB Output is correct
3 Correct 5 ms 9668 KB Output is correct
4 Correct 19 ms 13300 KB Output is correct
5 Correct 13 ms 11332 KB Output is correct
6 Correct 6 ms 9704 KB Output is correct
7 Correct 7 ms 9832 KB Output is correct
8 Correct 7 ms 9932 KB Output is correct
9 Correct 6 ms 9804 KB Output is correct
10 Correct 12 ms 11380 KB Output is correct
11 Correct 5 ms 9700 KB Output is correct
12 Correct 5 ms 9676 KB Output is correct
13 Correct 5 ms 9676 KB Output is correct
14 Correct 5 ms 9688 KB Output is correct
15 Correct 6 ms 9708 KB Output is correct

Subtask #4
45.0 / 45.0

# 결과 실행 시간 메모리 Grader output
1 Correct 261 ms 31492 KB Output is correct
2 Correct 339 ms 32312 KB Output is correct
3 Correct 359 ms 34616 KB Output is correct
4 Correct 280 ms 31932 KB Output is correct
5 Correct 322 ms 32824 KB Output is correct
6 Correct 310 ms 31544 KB Output is correct
7 Correct 317 ms 33220 KB Output is correct
8 Correct 328 ms 33080 KB Output is correct
9 Correct 287 ms 31532 KB Output is correct
10 Correct 245 ms 31436 KB Output is correct
11 Correct 113 ms 26760 KB Output is correct
12 Correct 278 ms 31704 KB Output is correct
13 Correct 324 ms 33524 KB Output is correct
14 Correct 376 ms 33328 KB Output is correct
15 Correct 373 ms 33196 KB Output is correct
16 Correct 368 ms 33524 KB Output is correct
17 Correct 356 ms 33648 KB Output is correct
18 Correct 309 ms 35048 KB Output is correct
19 Correct 347 ms 35728 KB Output is correct
20 Correct 311 ms 32988 KB Output is correct
21 Correct 308 ms 33512 KB Output is correct
22 Correct 320 ms 33244 KB Output is correct
23 Correct 139 ms 28228 KB Output is correct
24 Correct 292 ms 34848 KB Output is correct
25 Correct 14 ms 11564 KB Output is correct
26 Correct 5 ms 9676 KB Output is correct
27 Correct 5 ms 9668 KB Output is correct
28 Correct 19 ms 13300 KB Output is correct
29 Correct 13 ms 11332 KB Output is correct
30 Correct 6 ms 9704 KB Output is correct
31 Correct 7 ms 9832 KB Output is correct
32 Correct 7 ms 9932 KB Output is correct
33 Correct 6 ms 9804 KB Output is correct
34 Correct 12 ms 11380 KB Output is correct
35 Correct 5 ms 9700 KB Output is correct
36 Correct 5 ms 9676 KB Output is correct
37 Correct 5 ms 9676 KB Output is correct
38 Correct 5 ms 9688 KB Output is correct
39 Correct 6 ms 9708 KB Output is correct
40 Correct 297 ms 31432 KB Output is correct
41 Correct 312 ms 31420 KB Output is correct
42 Correct 346 ms 31572 KB Output is correct
43 Correct 167 ms 28996 KB Output is correct
44 Correct 157 ms 29120 KB Output is correct
45 Correct 369 ms 34620 KB Output is correct
46 Correct 399 ms 34308 KB Output is correct
47 Correct 318 ms 31928 KB Output is correct
48 Correct 153 ms 27292 KB Output is correct
49 Correct 241 ms 32220 KB Output is correct
50 Correct 328 ms 33916 KB Output is correct
51 Correct 376 ms 34600 KB Output is correct