Submission #931409

#	Time	Username	Problem	Language	Result	Execution time	Memory
931409		PieArmy	Robot (JOI21_ho_t4)	C++17	0 / 100	3036 ms	190024 KiB

Main

typedef long long ll;
ll pie(ll army){return (1ll<<army);}
#include <bits/stdc++.h>
#define fr first
#define sc second
#define pb push_back
#define endl '\n';
#define mid ((left+right)>>1)
const ll inf=2000000000000000005;
const int sonsuz=2000000005;
using namespace std;
ll fpow(ll x,ll y,ll m=0){if(y<0){cout<<"powError";return -1;}if(m)x%=m;ll res=1;while(y>0){if(y&1)res*=x;x*=x;if(m){x%=m;res%=m;}y>>=1;}return res;}
#define int ll
void code(){
    int n,m;cin>>n>>m;
    int C[m+1],P[m+1];
    vector<pair<int,int>>komsu[n+1];
    pair<int,int>kenar[m+1];
    pair<int,int>sira[m+1];
    vector<bool>dp[n+1];
    for(int i=1;i<=m;i++){
        int a,b;cin>>a>>b>>C[i]>>P[i];
        kenar[i].fr=a;
        kenar[i].sc=b;
        sira[i].fr=komsu[a].size();
        sira[i].sc=komsu[b].size();
        dp[a].pb(false);
        dp[b].pb(false);
        komsu[a].pb({b,i});
        komsu[b].pb({a,i});
    }
    for(int i=1;i<=n;i++)
        dp[i].pb(false);
    priority_queue<vector<int>>pq;
    pq.push({0,1,int(komsu[1].size())});
    int ans=inf;
    while(pq.size()){
        int pos=pq.top()[1],cos=-pq.top()[0],root=pq.top()[2];
        pq.pop();
        if(dp[pos][root])continue;
        dp[pos][root]=true;
        if(pos==n){
            ans=min(ans,cos);
            continue;
        }
        map<int,int>mp;
        for(int i=0;i<komsu[pos].size();i++){
            if(i==root)continue;
            mp[C[komsu[pos][i].sc]]+=P[komsu[pos][i].sc];
        }
        for(int i=0;i<komsu[pos].size();i++){
            if(i==root)continue;
            if(mp[C[komsu[pos][i].sc]]-P[komsu[pos][i].sc]<P[komsu[pos][i].sc]){
                pq.push({-cos-mp[C[komsu[pos][i].sc]]+P[komsu[pos][i].sc],komsu[pos][i].fr,int(komsu[komsu[pos][i].fr].size())});
            }
            else{
                int nex=sira[komsu[pos][i].sc].fr;
                if(kenar[komsu[pos][i].sc].fr==pos)nex=sira[komsu[pos][i].sc].sc;
                pq.push({-cos-P[komsu[pos][i].sc],komsu[pos][i].fr,nex});
            }
        }
    }
    if(ans==inf)cout<<-1;
    else cout<<ans;
}

int32_t main(){
    ios_base::sync_with_stdio(false);cin.tie(NULL);
    code();
    return 0;
}

Compilation message (stderr)

Main.cpp: In function 'void code()':
Main.cpp:47:22: warning: comparison of integer expressions of different signedness: 'll' {aka 'long long int'} and 'std::vector<std::pair<long long int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   47 |         for(int i=0;i<komsu[pos].size();i++){
      |                     ~^~~~~~~~~~~~~~~~~~
Main.cpp:51:22: warning: comparison of integer expressions of different signedness: 'll' {aka 'long long int'} and 'std::vector<std::pair<long long int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   51 |         for(int i=0;i<komsu[pos].size();i++){
      |                     ~^~~~~~~~~~~~~~~~~~

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