oj.uz

Submission #472509

# Submission time Handle Problem Language Result Execution time Memory
472509 2021-09-13T16:39:55 Z ZaZo_ Toll (BOI17_toll) C++14
10 / 100
 70 ms 4652 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;
    v.push_back({i,{a,b}});
  }
  int ans[o]={0};
  sort(v.begin(),v.end());
  for(int i = 0 ; i < v.size(); i ++){
    int a = v[i].second.first , b = v[i].second.second;
    if(!vis[a])
    {
      prepare();
      memset(vis,0,sizeof vis);
      djk(a,n);
    }
    if(dist[b]!=INT_MAX) ans[v[i].first]=dist[b];
    else ans[v[i].first]=-1;
  }
  for(int i = 0 ; i < o ; i++) cout<<ans[i]<<'\n';
}

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;
      |         ^
toll.cpp: In function 'int32_t main()':
toll.cpp:52:21: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, std::pair<int, int> > >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   52 |   for(int i = 0 ; i < v.size(); i ++){
      |                   ~~^~~~~~~~~~

Subtask #1
0 / 7.0

# Verdict Execution time Memory Grader output
1 Incorrect 28 ms 3820 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 3652 KB Output is correct
2 Correct 2 ms 1484 KB Output is correct
3 Correct 2 ms 1484 KB Output is correct
4 Correct 2 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 6 ms 1804 KB Output is correct
8 Correct 5 ms 1804 KB Output is correct
9 Correct 24 ms 3556 KB Output is correct
10 Correct 65 ms 4652 KB Output is correct
11 Correct 47 ms 3768 KB Output is correct
12 Correct 38 ms 3436 KB Output is correct
13 Correct 70 ms 4544 KB Output is correct
14 Correct 41 ms 3444 KB Output is correct
15 Correct 37 ms 3088 KB Output is correct
16 Correct 36 ms 3136 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 28 ms 3820 KB Output isn't correct
2 Halted 0 ms 0 KB -