Submission #783179

#	Time	Username	Problem	Language	Result	Execution time	Memory
783179		1075508020060209tc	Toll (BOI17_toll)	C++14	46 / 100	3039 ms	17228 KiB

toll

#include<bits/stdc++.h>
using namespace std;
#define int long long
#define X first
#define Y second
int K;int n;int m;int O;
vector<pair<int,int>>e[500005];
int dis0[500005];
int dis[500005];int vis[500005];


void dijkstera(int st){
for(int i=0;i<=n;i++){
    dis[i]=1e18;
}
dis[st]=0;
for(int i=st;i<=n-1;i++){
    for(int j=0;j<e[i].size();j++){
        int w=e[i][j].second;
        int v=e[i][j].first;
        dis[v]=min(dis[v],dis[i]+w);
    }
}
}

int ot(int v){
if(v>=1e18){
    return -1;
}
return v;
}

signed main(){
cin.tie(0);
ios_base::sync_with_stdio(0);
cin>>K>>n>>m>>O;
for(int i=1;i<=m;i++){
    int a;int b;int t;
    cin>>a>>b>>t;
    e[a].push_back({b,t});
}
dijkstera(0);
for(int i=0;i<=n;i++){
    dis0[i]=dis[i];
}
while(O--){
    int a;int b;
    cin>>a>>b;
    if(a==-1){
        cout<<ot(dis0[b])<<endl;
    }else{
        dijkstera(a);
        cout<<ot(dis[b])<<endl;
    }


}

}

Compilation message (stderr)

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

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