Submission #941887

#	Time	Username	Problem	Language	Result	Execution time	Memory
941887		Maite_Morale	Robot (JOI21_ho_t4)	C++14	0 / 100	216 ms	34104 KiB

Main

#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,pass[MAX];
vector<pair<ll,pll>> v[MAX]; 
ll distra(ll x,ll y){
    priority_queue<pll> q;
    q.push({0,x});
    while(!q.empty()){
        pll u=q.top();q.pop();
      //  cout<<u.S<<" "<<-u.F<<"\n";
        if(pass[u.S]!=0)continue;
        pass[u.S]=1;
        if(u.S==y)return -u.F;
        map<ll,ll> mp;
        for(auto w : v[u.S]){
            mp[w.S.F]+=w.S.S;
        }
        for(auto w : v[u.S]){
         //   cout<<"    "<<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});
        }
    }

return -1;
}
int main(){
    fast_in
    cin>>n>>m;ll a1,a2,a3,a4;
    for(int i=0;i<m;i++){
        cin>>a1>>a2>>a3>>a4;
        v[a1].push_back({a2,{a3,a4}});
        v[a2].push_back({a1,{a3,a4}});
    }
    cout<<distra(1,n);
return 0;
}

• Subtask 1: 0 / 34
• Subtask 2: 0 / 24
• Subtask 3: 0 / 42