제출 #533305

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
533305		Rafi22	Robot (JOI21_ho_t4)	C++14	0 / 100	3067 ms	67176 KiB

Main

#include <bits/stdc++.h>

using namespace std;

#define endl '\n'
#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];
ll d[N];
map<int,ll>sum[N];
map<int,ll>D[2][N];

int 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}});
        G[b].pb({a,{c,x}});
        sum[a][c]+=x;
        sum[b][c]+=x;
    }
    priority_queue<pair<ll,pair<int,int>>>Q;
    d[1]=1;
    for(int i=2;i<=n;i++) d[i]=infl;
    Q.push({-1,{1,0}});
    while(!Q.empty())
    {
        int v=Q.top().nd.st;
        int x=Q.top().nd.nd;
        int t=-Q.top().st;
        Q.pop();
        if(x==0)
        {
            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[0][u.st][u.nd.st]==0||t<D[0][u.st][u.nd.st])
                {
                    D[0][u.st][u.nd.st]=t;
                    Q.push({-(t),{u.st,u.nd.st}});
                }
                X=sum[v][u.nd.st]-u.nd.nd;
                if(D[1][u.st][u.nd.st]==0||t+X<D[1][u.st][u.nd.st])
                {
                    D[1][u.st][u.nd.st]=t+X;
                    Q.push({-(t+X),{u.st,-u.nd.st}});
                }
            }
        }
        if(x>0)
        {
            for(auto u:G[v])
            {
                if(u.nd.st!=x) continue;
                ll X=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}});
                }
                if(D[1][u.st][u.nd.st]==0||t+X<D[1][u.st][u.nd.st])
                {
                    D[1][u.st][u.nd.st]=t+X;
                    Q.push({-(t+X),{u.st,-u.nd.st}});
                }
            }
        }
        if(x<0)
        {
            for(auto u:G[v])
            {
                if(u.nd.st!=x) continue;
                if(t<d[u.st])
                {
                    d[u.st]=t;
                    Q.push({-(t),{u.st,0}});
                }
                if(D[0][u.st][u.nd.st]==0||t-u.nd.nd<D[0][u.st][u.nd.st])
                {
                    D[0][u.st][u.nd.st]=t-u.nd.nd;
                    Q.push({-(t-u.nd.nd),{u.st,u.nd.st}});
                }
            }
        }
    }
    if(d[n]==infl) cout<<-1;
    else cout<<d[n]-1;

    return 0;
}

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