# |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
941915 |
2024-03-09T16:52:20 Z |
Maite_Morale |
Robot (JOI21_ho_t4) |
C++14 |
|
443 ms |
131812 KB |
#include<bits/stdc++.h>
#define F first
#define S second
#define MAX 500005
#define oo 1e18
#define mod 1000000007
#define fast_in ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);cout.setf(ios::fixed);cout.precision(0);
using namespace std;
typedef long long ll;
#define pll pair<ll , ll>
#define vll vector<ll>
#define vvll vector<vll>
#define vpll vector<pll>
ll m,n,ans=oo;
vll pass[MAX];
map<ll,ll> node[MAX];
vector<pair<ll,pll>> v[MAX];
ll distra(ll x,ll y){
priority_queue<pair<ll,pll>> q;
q.push({0,{x,0}});
while(!q.empty()){
pair<ll,pll> u=q.top();q.pop();
// cerr<<u.S.F<<" "<<u.S.S<<": "<<-u.F<<"\n";
if(pass[u.S.F][node[u.S.F][u.S.S]]!=0)continue;
pass[u.S.F][node[u.S.F][u.S.S]]=1;
if(u.S.F==y){
if(ans==oo)ans=-u.F;
else ans=min(ans,-u.F);
}
// if(u.S==y)return -u.F;
map<ll,ll> mp;
for(auto w : v[u.S.F]){
if(w.F==u.S.S || w.F==0)continue;
mp[w.S.F]+=w.S.S;
}//cerr<<".";
for(auto w : v[u.S.F]){
if(w.F==u.S.S || w.F==0)continue;
// cerr<<" "<<w.F<<" "<<min(w.S.S,mp[w.S.F]-w.S.S)<<"\n";
q.push({u.F-min(w.S.S,mp[w.S.F]-w.S.S),{w.F,u.S.F}});
}
}
}
int main(){
fast_in
cin>>n>>m;ll a1=1,a2=0,a3=0,a4=0;
node[a1][a2]=v[a1].size();
v[a1].push_back({a2,{a3,a4}});
for(int i=0;i<m;i++){
cin>>a1>>a2>>a3>>a4;
node[a1][a2]=v[a1].size();
node[a2][a1]=v[a2].size();
v[a1].push_back({a2,{a3,a4}});
v[a2].push_back({a1,{a3,a4}});
pass[a1].push_back(0);
pass[a2].push_back(0);
}distra(1,n);
if(ans==oo)cout<<-1;
else cout<<ans;
return 0;
}
Compilation message
Main.cpp: In function 'll distra(ll, ll)':
Main.cpp:44:1: warning: no return statement in function returning non-void [-Wreturn-type]
44 | }
| ^
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Runtime error |
49 ms |
95756 KB |
Execution killed with signal 11 |
2 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Runtime error |
443 ms |
131812 KB |
Execution killed with signal 11 |
2 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Runtime error |
49 ms |
95756 KB |
Execution killed with signal 11 |
2 |
Halted |
0 ms |
0 KB |
- |