oj.uz

Submission #528506

# Submission time Handle Problem Language Result Execution time Memory
528506 2022-02-20T12:13:50 Z georgerapeanu Commuter Pass (JOI18_commuter_pass) C++11
100 / 100
 548 ms 33236 KB 
#include <bits/stdc++.h>

using namespace std;

const long long inf = 1e18;

vector<long long> dijkstra(int source, const vector<vector<pair<int, long long> > > &graph){
  vector<long long> dist(graph.size(), inf);
  dist[source] = 0;
  priority_queue<pair<long long, int>, vector<pair<long long, int> >, greater<pair<long long, int> > > pq;

  pq.push({dist[source], source});

  while(!pq.empty()){
    int nod = pq.top().second;
    long long cost = pq.top().first;
    pq.pop();
    if(cost != dist[nod]){
      continue;
    }
    for(auto it:graph[nod]){
      if(dist[it.first] > dist[nod] + it.second){
        dist[it.first] = dist[nod] + it.second;
        pq.push({dist[it.first], it.first});
      }
    }
  }

  return dist;
}

long long best_distance(const vector<long long> &dist_u, const vector<long long> &dist_v, vector<vector<pair<int, long long> > > &graph, const vector<pair<int,int> > &edges, int n){
//  for(auto it:dist_u)printf("%lld ", it);printf("\n");
//  for(auto it:dist_v)printf("%lld ", it);printf("\n");
  for(int i = 0;i < n;i++){
    graph[i].clear();
  }

  for(auto it:edges){
      graph[it.first].push_back({it.second, dist_v[it.second] - dist_v[it.first]});
  //    printf("edge from %d to %d with cost %lld\n", it.first, it.second, dist_v[it.second] - dist_v[it.first]);
  }
  
  if((int)graph.size() < n + 1){
    graph.push_back(vector<pair<int, long long> >());
  }else{
    graph[n].clear();
  }
  for(int i = 0;i < n;i++){
    graph[n].push_back({i, dist_u[i] + dist_v[i]});
  //  printf("edge from %d to %d with cost %lld\n", n, i, dist_u[i] + dist_v[i]);
  }
  //printf("\n");
  
  vector<long long> dist = dijkstra(n, graph); 

  long long best_dist = inf;

  for(int i = 0;i < n;i++){
    best_dist = min(best_dist, dist[i]);
  }
  return best_dist;
}

int main(){
  int n, m;
  int s, t;
  int u, v;

  scanf("%d %d", &n, &m);
  scanf("%d %d", &s, &t);
  scanf("%d %d", &u, &v);

  s--;
  v--;
  t--;
  u--;

  vector<vector<pair<int, long long> > > graph(n, vector<pair<int, long long> >());
  vector<pair<pair<int, int>,int> > edges;


  for(int i = 1;i <= m;i++){
    int a, b, c;
    scanf("%d %d %d", &a, &b, &c);
    a--;
    b--;
    graph[a].push_back({b, c});
    graph[b].push_back({a, c});
    edges.push_back({{a, b}, c});
  }

  vector<long long> dist_s = dijkstra(s, graph);
  vector<long long> dist_t = dijkstra(t, graph);
  
  vector<long long> dist_u = dijkstra(u, graph);
  vector<long long> dist_v = dijkstra(v, graph);

  vector<pair<int, int> > new_edges;

  for(auto it:edges){
    if(dist_t[it.first.first] + dist_s[it.first.second] + it.second == dist_s[t]){
      new_edges.push_back({it.first.second, it.first.first});
    }
    if(dist_s[it.first.first] + dist_t[it.first.second] + it.second == dist_s[t]){
      new_edges.push_back({it.first.first, it.first.second});
    }
  }

  long long fst = best_distance(dist_u, dist_v, graph, new_edges, n);
  long long snd = best_distance(dist_v, dist_u, graph, new_edges, n);
  long long trd = dist_u[v];
 
  printf("%lld\n", min(min(fst, snd), trd));
  
  return 0;
}

Compilation message

commuter_pass.cpp: In function 'int main()':
commuter_pass.cpp:70:8: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   70 |   scanf("%d %d", &n, &m);
      |   ~~~~~^~~~~~~~~~~~~~~~~
commuter_pass.cpp:71:8: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   71 |   scanf("%d %d", &s, &t);
      |   ~~~~~^~~~~~~~~~~~~~~~~
commuter_pass.cpp:72:8: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   72 |   scanf("%d %d", &u, &v);
      |   ~~~~~^~~~~~~~~~~~~~~~~
commuter_pass.cpp:85:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   85 |     scanf("%d %d %d", &a, &b, &c);
      |     ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~

Subtask #1
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 316 ms 24644 KB Output is correct
2 Correct 387 ms 28768 KB Output is correct
3 Correct 412 ms 29044 KB Output is correct
4 Correct 326 ms 28508 KB Output is correct
5 Correct 473 ms 28860 KB Output is correct
6 Correct 361 ms 28524 KB Output is correct
7 Correct 483 ms 28948 KB Output is correct
8 Correct 453 ms 28648 KB Output is correct
9 Correct 347 ms 29008 KB Output is correct
10 Correct 282 ms 29088 KB Output is correct
11 Correct 185 ms 20812 KB Output is correct
12 Correct 338 ms 28968 KB Output is correct

Subtask #2
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 345 ms 25132 KB Output is correct
2 Correct 404 ms 28480 KB Output is correct
3 Correct 337 ms 28720 KB Output is correct
4 Correct 402 ms 28492 KB Output is correct
5 Correct 391 ms 28776 KB Output is correct
6 Correct 362 ms 28928 KB Output is correct
7 Correct 499 ms 29024 KB Output is correct
8 Correct 388 ms 28496 KB Output is correct
9 Correct 445 ms 28684 KB Output is correct
10 Correct 354 ms 28496 KB Output is correct
11 Correct 202 ms 20956 KB Output is correct
12 Correct 356 ms 28864 KB Output is correct

Subtask #3
24.0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 2056 KB Output is correct
2 Correct 1 ms 292 KB Output is correct
3 Correct 1 ms 332 KB Output is correct
4 Correct 17 ms 4328 KB Output is correct
5 Correct 9 ms 2272 KB Output is correct
6 Correct 1 ms 460 KB Output is correct
7 Correct 2 ms 460 KB Output is correct
8 Correct 2 ms 580 KB Output is correct
9 Correct 1 ms 460 KB Output is correct
10 Correct 9 ms 2304 KB Output is correct
11 Correct 1 ms 332 KB Output is correct
12 Correct 1 ms 284 KB Output is correct
13 Correct 1 ms 296 KB Output is correct
14 Correct 1 ms 332 KB Output is correct
15 Correct 1 ms 332 KB Output is correct

Subtask #4
45.0 / 45.0

# Verdict Execution time Memory Grader output
1 Correct 316 ms 24644 KB Output is correct
2 Correct 387 ms 28768 KB Output is correct
3 Correct 412 ms 29044 KB Output is correct
4 Correct 326 ms 28508 KB Output is correct
5 Correct 473 ms 28860 KB Output is correct
6 Correct 361 ms 28524 KB Output is correct
7 Correct 483 ms 28948 KB Output is correct
8 Correct 453 ms 28648 KB Output is correct
9 Correct 347 ms 29008 KB Output is correct
10 Correct 282 ms 29088 KB Output is correct
11 Correct 185 ms 20812 KB Output is correct
12 Correct 338 ms 28968 KB Output is correct
13 Correct 345 ms 25132 KB Output is correct
14 Correct 404 ms 28480 KB Output is correct
15 Correct 337 ms 28720 KB Output is correct
16 Correct 402 ms 28492 KB Output is correct
17 Correct 391 ms 28776 KB Output is correct
18 Correct 362 ms 28928 KB Output is correct
19 Correct 499 ms 29024 KB Output is correct
20 Correct 388 ms 28496 KB Output is correct
21 Correct 445 ms 28684 KB Output is correct
22 Correct 354 ms 28496 KB Output is correct
23 Correct 202 ms 20956 KB Output is correct
24 Correct 356 ms 28864 KB Output is correct
25 Correct 9 ms 2056 KB Output is correct
26 Correct 1 ms 292 KB Output is correct
27 Correct 1 ms 332 KB Output is correct
28 Correct 17 ms 4328 KB Output is correct
29 Correct 9 ms 2272 KB Output is correct
30 Correct 1 ms 460 KB Output is correct
31 Correct 2 ms 460 KB Output is correct
32 Correct 2 ms 580 KB Output is correct
33 Correct 1 ms 460 KB Output is correct
34 Correct 9 ms 2304 KB Output is correct
35 Correct 1 ms 332 KB Output is correct
36 Correct 1 ms 284 KB Output is correct
37 Correct 1 ms 296 KB Output is correct
38 Correct 1 ms 332 KB Output is correct
39 Correct 1 ms 332 KB Output is correct
40 Correct 294 ms 28060 KB Output is correct
41 Correct 329 ms 28864 KB Output is correct
42 Correct 309 ms 28968 KB Output is correct
43 Correct 282 ms 21328 KB Output is correct
44 Correct 284 ms 21324 KB Output is correct
45 Correct 548 ms 33236 KB Output is correct
46 Correct 510 ms 29364 KB Output is correct
47 Correct 356 ms 28472 KB Output is correct
48 Correct 258 ms 20892 KB Output is correct
49 Correct 301 ms 27532 KB Output is correct
50 Correct 455 ms 29376 KB Output is correct
51 Correct 350 ms 29932 KB Output is correct