This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#pragma optimize("unroll-loops")
#include<bits/stdc++.h>
using namespace std;
#define maxn 50050
#define f first
#define s second
vector<vector<pair<int,int> > > adj(maxn);
vector<int> top;
vector<int> visited(maxn,0);
void topsort(int node){
visited[node] = 1;
for(auto k:adj[node]){
if(visited[k.f]==1){
continue;
}
topsort(k.f);
}
top.push_back(node);
}
int32_t main(){
ios::sync_with_stdio(0);
cin.tie(0);cout.tie(0);
int k,no_of_vertex,no_of_edge,no_of_query;
int input1,input2,input3;
cin >> k >> no_of_vertex >> no_of_edge >> no_of_query;
for(int i=0;i<no_of_edge;i++){
cin >> input1 >> input2 >> input3;
adj[input1].push_back({input2,input3});
}
for(int i=0;i<no_of_vertex;i++){
if(visited[i]==0){
topsort(i);
}
}
reverse(top.begin(),top.end());
vector<int> dist(maxn,INT_MAX);
for(int i=0;i<no_of_query;i++){
cin >> input1 >> input2;
for(int j=0;j<dist.size();j++){
dist[j] = INT_MAX;
}
int pos = -1;
for(int j=0;j<top.size();j++){
if(top[j]==input1){
pos = j;
break;
}
}
dist[input1] = 0;
for(int j=pos;j<top.size();j++){
if(dist[top[j]]==INT_MAX){
continue;
}
for(auto kk:adj[top[j]]){
if(dist[kk.first]>dist[top[j]]+kk.second){
dist[kk.first] = dist[top[j]]+kk.second;
}
}
}
if(dist[input2]==INT_MAX){
cout << -1 << "\n";
}
else{
cout << dist[input2] << "\n";
}
}
}
Compilation message (stderr)
toll.cpp:1:0: warning: ignoring #pragma optimize [-Wunknown-pragmas]
#pragma optimize("unroll-loops")
toll.cpp: In function 'int32_t main()':
toll.cpp:39:22: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for(int j=0;j<dist.size();j++){
~^~~~~~~~~~~~
toll.cpp:43:22: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for(int j=0;j<top.size();j++){
~^~~~~~~~~~~
toll.cpp:50:24: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for(int j=pos;j<top.size();j++){
~^~~~~~~~~~~
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |