This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#include"bits/stdc++.h"
using namespace std;
#define ll long long
#define endl "\n"
#define fastio ios_base::sync_with_stdio(false)
#define inf LLONG_MAX
const ll lmt=202;
vector<pair<ll,ll>>adj[lmt][2];
ll dis[lmt][2][2];
int main(){
fastio;
ll n,m;
cin>>n>>m;
for(ll i=1;i<=m;i++){
ll u,v,c,d;
cin>>u>>v>>c>>d;
adj[u][0].push_back({c,v});
adj[v][1].push_back({c+d,u});
}
for(ll i=0;i<=n;i++){
for(ll j=0;j<2;j++) for(ll k=0;k<2;k++) dis[i][j][k]=inf;
}
set<array<ll,4>>q;
q.insert({0,1,0,0});
while(!q.empty()){
auto it=q.begin();
ll val=(*it)[0],u=(*it)[1],ver=(*it)[2],ver2=(*it)[3];
q.erase(it);
if(dis[u][ver][ver2]<val) continue;
for(auto [w,v]:adj[u][0]){
if(v==n){
if(dis[v][ver][1]>val+w){
q.erase({dis[v][ver][1],v,ver,1});
dis[v][ver][1]=val+w;
q.insert({dis[v][ver][1],v,ver,1});
}
}else{
if(dis[v][ver][ver2]>val+w){
q.erase({dis[v][ver][ver2],v,ver,ver2});
dis[v][ver][ver2]=val+w;
q.insert({dis[v][ver][ver2],v,ver,ver2});
}
}
}
if(ver) continue;
for(auto [w,v]:adj[u][1]){
if(v==n){
if(dis[v][1][1]>val+w){
q.erase({dis[v][1][1],v,1,1});
dis[v][1][1]=val+w;
q.insert({dis[v][ver][1],v,1,1});
}
}else{
if(dis[v][1][ver2]>val+w){
q.erase({dis[v][1][ver2],v,1,ver2});
dis[v][1][ver2]=val+w;
q.insert({dis[v][1][ver2],v,1,ver2});
}
}
}
}
ll ans=min(dis[1][0][1],dis[1][1][1]);
if(ans==inf) ans=-1;
cout<<ans<<endl;
return 0;
}
Compilation message (stderr)
ho_t4.cpp: In function 'int main()':
ho_t4.cpp:40:12: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
40 | for(auto [w,v]:adj[u][0]){
| ^
ho_t4.cpp:58:12: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
58 | for(auto [w,v]:adj[u][1]){
| ^
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |