oj.uz

Submission #472506

# Submission time Handle Problem Language Result Execution time Memory
472506 2021-09-13T16:36:51 Z ZaZo_ Toll (BOI17_toll) C++14
10 / 100
 83 ms 4356 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],vis[50001]={0};
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;
    vis[u]=1;
    pq.pop();
    for(int i = 0 ; i < edges[u].size() ; i++)
    {
      if(!vis[edges[u][i].first]&&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(!vis[a])
    {
      prepare();
      memset(vis,0,sizeof vis);
      djk(a,n);
    }
    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:22: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]
   22 |     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 42 ms 3396 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 61 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 1484 KB Output is correct
6 Correct 1 ms 1484 KB Output is correct
7 Correct 19 ms 1552 KB Output is correct
8 Correct 19 ms 1568 KB Output is correct
9 Correct 38 ms 3164 KB Output is correct
10 Correct 83 ms 4320 KB Output is correct
11 Correct 62 ms 3396 KB Output is correct
12 Correct 49 ms 3096 KB Output is correct
13 Correct 71 ms 4356 KB Output is correct
14 Correct 49 ms 3312 KB Output is correct
15 Correct 40 ms 3096 KB Output is correct
16 Correct 41 ms 2992 KB Output is correct

Subtask #3
0 / 8.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 1612 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 1612 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #5
0 / 44.0

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