Submission #720239

#TimeUsernameProblemLanguageResultExecution timeMemory
720239Ahmed57Ceste (COCI17_ceste)C++14
0 / 160
519 ms131072 KiB
#include <bits/stdc++.h> using namespace std; #define int long long long long cost[2005][2005]; vector<pair<int,pair<int,int>>> adj[2005]; signed main(){ int n,m; cin>>n>>m; //if(n<=100)assert(0); for(int i = 0;i<=n;i++){ for(int j = 0;j<=2004;j++){ cost[i][j] = 1e15; } } for(int i = 0;i<m;i++){ int a,b,c,d; cin>>a>>b>>c>>d; adj[a].push_back({b,{c,d}}); adj[b].push_back({a,{c,d}}); } priority_queue<pair<int,pair<int,int>>> q; q.push({0,{0,1}}); cost[1][0]=0; while(!q.empty()){ int no = q.top().second.second; int se = q.top().second.first; int co = -q.top().first; q.pop(); if(cost[no][se]<co)continue; for(auto j:adj[no]){ if(co+j.second.second>2004)continue; if(cost[j.first][se+j.second.first]>co+j.second.second){ cost[j.first][se+j.second.first] = co+j.second.second; q.push({-cost[j.first][se+j.second.first],{se+j.second.first,j.first}}); } } } for(int i = 2;i<=n;i++){ long long ans = 1e15; for(long long j = 1;j<=2004;j++){ ans = min(ans,j*cost[i][j]); } if(ans>=1e15){ cout<<"-1"<<endl; } else cout<<ans<<endl; } }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...