oj.uz

Submission #472496

# Submission time Handle Problem Language Result Execution time Memory
472496 2021-09-13T16:23:53 Z ZaZo_ Toll (BOI17_toll) C++14
8 / 100
 3000 ms 6212 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 djk(int s , int e)
{
  int dist[n+1];
  for(int i = 0 ; i < n+1 ; i ++) dist[i]=1e15;
  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] > edges[u][i].second + c)
      {
        dist[edges[u][i].first] = edges[u][i].second+c;
      //  cout<<dist[edges[u][i].first]<<endl;
        pq.push({-dist[edges[u][i].first],edges[u][i].first});
      }
    }
  }
  return dist[e];
}
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});
  }
  while(o--)
  {
    int a , b;
    cin >> a >> b;
    int ans=djk(a,b);
    if(ans==1e15) cout<<"-1"<<endl;
    else
    cout<<ans<<endl;
  }
}

Compilation message

toll.cpp: In function 'long long int djk(long long int, long long int)':
toll.cpp:18:23: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<std::pair<long long int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   18 |     for(int i = 0 ; i < edges[u].size() ; i++)
      |                     ~~^~~~~~~~~~~~~~~~~

Subtask #1
0 / 7.0

# Verdict Execution time Memory Grader output
1 Execution timed out 3067 ms 3568 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #2
0 / 10.0

# Verdict Execution time Memory Grader output
1 Execution timed out 3064 ms 4512 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #3
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 1484 KB Output is correct
2 Correct 1 ms 1356 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 2 ms 1484 KB Output is correct
7 Correct 5 ms 1484 KB Output is correct
8 Correct 15 ms 1612 KB Output is correct
9 Correct 10 ms 1484 KB Output is correct
10 Correct 28 ms 3316 KB Output is correct
11 Correct 278 ms 4292 KB Output is correct
12 Correct 394 ms 5756 KB Output is correct
13 Correct 459 ms 6212 KB Output is correct
14 Correct 382 ms 5124 KB Output is correct
15 Correct 246 ms 3672 KB Output is correct
16 Correct 243 ms 3648 KB Output is correct

Subtask #4
0 / 31.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 1484 KB Output is correct
2 Correct 1 ms 1356 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 2 ms 1484 KB Output is correct
7 Correct 5 ms 1484 KB Output is correct
8 Correct 15 ms 1612 KB Output is correct
9 Correct 10 ms 1484 KB Output is correct
10 Correct 28 ms 3316 KB Output is correct
11 Correct 278 ms 4292 KB Output is correct
12 Correct 394 ms 5756 KB Output is correct
13 Correct 459 ms 6212 KB Output is correct
14 Correct 382 ms 5124 KB Output is correct
15 Correct 246 ms 3672 KB Output is correct
16 Correct 243 ms 3648 KB Output is correct
17 Execution timed out 3036 ms 4508 KB Time limit exceeded
18 Halted 0 ms 0 KB -

Subtask #5
0 / 44.0

# Verdict Execution time Memory Grader output
1 Execution timed out 3067 ms 3568 KB Time limit exceeded
2 Halted 0 ms 0 KB -