Submission #533316

#	Time	Username	Problem	Language	Result	Execution time	Memory
533316		Rafi22	Robot (JOI21_ho_t4)	C++14	100 / 100	1066 ms	120572 KiB

Main

#include <bits/stdc++.h>

using namespace std;

#define endl '\n'
#define int long long
#define st first
#define nd second
#define pb push_back
#define sz(x) (int)(x).size()
#define all(x) (x).begin(), (x).end()
#define ll long long
ll mod=1000000007;
int inf=1000000007;
ll infl=1000000000000000007;

const int N=100007;

vector<pair<int,pair<int,ll>>>G[N];
map<int,vector<pair<int,ll>>>G1[N];
ll d[N];
map<int,ll>sum[N];
bool odw[N];
map<int,ll>D[N];
map<int,ll>was[N];

signed main()
{
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    int n,m,a,b,c;
    ll x;
    cin>>n>>m;
    for(int i=0;i<m;i++)
    {
        cin>>a>>b>>c>>x;
        G[a].pb({b,{c,x}});
        G1[a][c].pb({b,x});
        G[b].pb({a,{c,x}});
        G1[b][c].pb({a,x});
        sum[a][c]+=x;
        sum[b][c]+=x;
    }
    priority_queue<pair<ll,pair<int,int>>>Q;
    d[1]=inf;
    for(int i=2;i<=n;i++) d[i]=infl;
    Q.push({-inf,{1,0}});
    while(!Q.empty())
    {
        int v=Q.top().nd.st;
        int x=Q.top().nd.nd;
        ll t=-Q.top().st;
        Q.pop();
        if(x==0)
        {
            if(odw[v]) continue;
            odw[v]=1;
            for(auto u:G[v])
            {
                ll X=min(u.nd.nd,sum[v][u.nd.st]-u.nd.nd);
                if(t+X<d[u.st])
                {
                    d[u.st]=t+X;
                    Q.push({-(t+X),{u.st,0}});
                }
                X=u.nd.nd;
                if(D[u.st][u.nd.st]==0||t<D[u.st][u.nd.st])
                {
                    D[u.st][u.nd.st]=t;
                    Q.push({-(t),{u.st,u.nd.st}});
                }
            }
        }
        if(x>0)
        {
            if(was[v][x]) continue;
            was[v][x]=1;
            for(auto u:G1[v][x])
            {
                ll X=sum[v][x]-u.nd;
                if(t+X<d[u.st])
                {
                    d[u.st]=t+X;
                    Q.push({-(t+X),{u.st,0}});
                }
            }
        }
    }
    if(d[n]==infl) cout<<-1;
    else cout<<d[n]-inf;

    return 0;
}

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