oj.uz

Submission #472503

# Submission time Handle Problem Language Result Execution time Memory
472503 2021-09-13T16:29:07 Z ZaZo_ Toll (BOI17_toll) C++14
10 / 100
 76 ms 4308 KB 
#include <bits/stdc++.h>
#define ZAZO ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
//#define int long long
using namespace std;
vector<pair<int,int>>edges[50001];
int k , n , m , o ;
int dist[50001];
void prepare()
{
  for(int i = 0 ; i < n+1 ; i ++) dist[i]=INT_MAX;
}
void djk(int s , int e)
{
  priority_queue<pair<int,int>>pq;
  dist[s]=0;
  pq.push({0,s});
  while(!pq.empty())
  {
    int c = -pq.top().first , u = pq.top().second;
    pq.pop();
    for(int i = 0 ; i < edges[u].size() ; i++)
    {
      if(dist[edges[u][i].first] > dist[u] + edges[u][i].second)
      {
        dist[edges[u][i].first] = dist[u] + edges[u][i].second;
        pq.push({-dist[edges[u][i].first],edges[u][i].first});
      }
    }
  }
}
int32_t main() {
  ZAZO
  cin >> k >> n >> m >> o ;
  for(int i = 0 ; i < m ; i ++)
  {
    int a , b , t;
    cin >> a >> b >> t;
    edges[a].push_back({b,t});
  }
  vector<pair<int,pair<int,int>>>v;
  prepare();
  djk(0,n);
  for(int i = 0 ; i < o ; i ++)
  {
    int a , b;
    cin >> a >> b;
    if(dist[b]!=INT_MAX) cout<<dist[b]<<endl;
    else cout<<"-1"<<endl;
  }
}

Compilation message

toll.cpp: In function 'void djk(int, int)':
toll.cpp:21:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   21 |     for(int i = 0 ; i < edges[u].size() ; i++)
      |                     ~~^~~~~~~~~~~~~~~~~
toll.cpp:19:9: warning: unused variable 'c' [-Wunused-variable]
   19 |     int c = -pq.top().first , u = pq.top().second;
      |         ^

Subtask #1
0 / 7.0

# Verdict Execution time Memory Grader output
1 Incorrect 41 ms 3276 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 55 ms 3280 KB Output is correct
2 Correct 1 ms 1484 KB Output is correct
3 Correct 1 ms 1484 KB Output is correct
4 Correct 1 ms 1484 KB Output is correct
5 Correct 1 ms 1356 KB Output is correct
6 Correct 1 ms 1484 KB Output is correct
7 Correct 19 ms 1560 KB Output is correct
8 Correct 19 ms 1576 KB Output is correct
9 Correct 39 ms 3260 KB Output is correct
10 Correct 76 ms 4204 KB Output is correct
11 Correct 59 ms 3228 KB Output is correct
12 Correct 49 ms 3120 KB Output is correct
13 Correct 74 ms 4308 KB Output is correct
14 Correct 44 ms 3288 KB Output is correct
15 Correct 40 ms 2864 KB Output is correct
16 Correct 37 ms 2872 KB Output is correct

Subtask #3
0 / 8.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 1484 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
0 / 31.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 1484 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #5
0 / 44.0

# Verdict Execution time Memory Grader output
1 Incorrect 41 ms 3276 KB Output isn't correct
2 Halted 0 ms 0 KB -