Submission #854232

#	Time	Username	Problem	Language	Result	Execution time	Memory
854232		LeVanThuc	Robot (JOI21_ho_t4)	C++17	100 / 100	811 ms	125384 KiB

Main

#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define fi first
#define se second
#define p(x,y) pair<ll,ll>(x,y)
#define BIT(i,x) ((x>>i)&1)
#define MASK(x) (1<<x)
#define ld long double
#define __builtin_popcount __builtin_popcountll
#define pll pair<ll,ll>
template<class T1,class T2>
bool maximize(T1 &x,const T2 &y)
{
    if(x<y)
    {
        x=y;
        return 1;
    }
    return 0;
}
template<class T1,class T2>
bool minimize(T1 &x,const T2 &y)
{
    if(x>y)
    {
        x=y;
        return 1;
    }
    return 0;
}
void online()
{
    std::ios_base::sync_with_stdio(0);
    cin.tie(0);
#ifdef thuc
    freopen("input.INP","r",stdin);
    freopen("output.OUT","w",stdout);
#endif
}
const ll N=2e5+10,inf=1e18;
map<ll,vector<pll> > gr[N];
map<ll,ll> f1[N],sum[N],vs[N];
ll f[N];
ll n,m;
struct info
{
    ll d,u,s;
    info(ll _d=0,ll _u=0,ll _s=0)
    {
        d=_d;
        u=_u;
        s=_s;
    }
    bool operator <(const info &o) const
    {
        return d>o.d;
    }
};
int main()
{
    online();
    cin>>n>>m;
    for(int i=1; i<=m; i++)
    {
        ll u,v,c,s;
        cin>>u>>v>>c>>s;
        gr[u][c].emplace_back(v,s);
        gr[v][c].emplace_back(u,s);
        sum[u][c]+=s;
        sum[v][c]+=s;
    }
    priority_queue<info> qq;
    memset(f,0x3f,sizeof f);
    f[1]=0;
    qq.emplace(0,1,0);
    while(qq.size())
    {
        auto [d,u,s]=qq.top();
        qq.pop();
        if(!s)
        {
            if(d!=f[u]) continue;
            for(auto &[c,adj]:gr[u])
            {
                for(auto [v,w]:adj)
                {
                        if(minimize(f[v],f[u]+sum[u][c]-w))
                        {
                            qq.emplace(f[v],v,0);
                        }
                        if(minimize(f[v],f[u]+w))
                        {
                            qq.emplace(f[v],v,0);
                        }
                        if(vs[v][c]==0||minimize(f1[v][c],f[u]))
                        {
                            vs[v][c]=1;
                            f1[v][c]=f[u];
                            qq.emplace(f1[v][c],v,c);
                        }
                }
            }
        }
        else
        {
            if(d!=f1[u][s]) continue;
            ll c=s;
            for(auto [v,w]:gr[u][s])
            {
                if(minimize(f[v],f1[u][s]+sum[u][c]-w))
                {
                    qq.emplace(f[v],v,0);
                }
            }
        }
    }
    if(f[n]>1e18) f[n]=-1;
    cout<<f[n];
}

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