Submission #244653

#	Time	Username	Problem	Language	Result	Execution time	Memory
244653		kimbj0709	Toll (BOI17_toll)	C++14	8 / 100	3099 ms	6144 KiB

toll

#pragma GCC optimization("O3")
#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(auto kk:top){
        cout << kk << " ";
    }
    cout << "--\n";*/
    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 GCC optimization [-Wunknown-pragmas]
 #pragma GCC optimization("O3")
 
toll.cpp: In function 'int32_t main()':
toll.cpp:43:22: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
         for(int j=0;j<dist.size();j++){
                     ~^~~~~~~~~~~~
toll.cpp:47:22: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
         for(int j=0;j<top.size();j++){
                     ~^~~~~~~~~~~
toll.cpp:54:24: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
         for(int j=pos;j<top.size();j++){
                       ~^~~~~~~~~~~

• Subtask 1: 0 / 7
• Subtask 2: 0 / 10
• Subtask 3: 8 / 8
• Subtask 4: 0 / 31
• Subtask 5: 0 / 44