Submission #628684

#	Time	Username	Problem	Language	Result	Execution time	Memory
628684		Iwanttobreakfree	Toll (BOI17_toll)	C++17	10 / 100	136 ms	5852 KiB

toll

#include <iostream>
#include <vector>
#include <queue>
using namespace std;
#define int long long
void dijkstra(int a,vector<vector<pair<int,int>>>& g,vector<int>& dist){
    for(int i=0;i<dist.size();i++)dist[i]=1e18;
    dist[a]=0;
    priority_queue<pair<int,int>> pq;
    pq.push({0,a});
    while(pq.size()){
        int u=pq.top().second,d=-pq.top().first;
        pq.pop();
        if(d>dist[u])continue;
        for(auto v:g[u]){
            if(dist[v.first]>dist[u]+v.second){
                dist[v.first]=dist[u]+v.second;
                pq.push({-dist[v.first],v.first});
            }
        }
    }
}
signed main(){
    int n,m,o,k,x,y,w;
    cin>>k>>n>>m>>o;
    vector<vector<pair<int,int>>> g(n,vector<pair<int,int>>());
    vector<long long> dist(n,1e18);
    while(m--){
        cin>>x>>y>>w;
        //x--;y--;
        g[x].push_back({y,w});
        //g[y].push_back({x,w});
    }
    dijkstra(0,g,dist);
    while(o--){
        cin>>x>>y;
        if(dist[y]==1e18)cout<<-1<<'\n';
        else cout<<dist[y]<<'\n';
    }
}

Compilation message (stderr)

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

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