Submission #1181049

#	Time	Username	Problem	Language	Result	Execution time	Memory
1181049		Szymon_Pilipczuk	Olympic Bus (JOI20_ho_t4)	C++20	5 / 100	1095 ms	3840 KiB

ho_t4

#include <bits/stdc++.h>
using namespace std;
#define ll long long
ll infl = 1e18;
ll ans;
vector<vector<vector<ll>>> gr;
ll co[200][2];
priority_queue<vector<ll>,vector<vector<ll>>,greater<vector<ll>>> pq;
void dk(int p,ll c,int t)
{
    //cout<<p<<" "<<c<<" "<<t<<"\n";
    for(int i = 0;i<gr[p].size();i++)
    {
        /*if(p == 2 && t == 1)
        {
            cout<<gr[p][i][0]<<" "<<gr[p][i][1]<<"\n";
        }*/
        if(co[gr[p][i][0]][t] > c + gr[p][i][1])
        {
            co[gr[p][i][0]][t] = c + gr[p][i][1];
            pq.push({c + gr[p][i][1],gr[p][i][0],t});
        }
    }
}
int main()
{
    int n,m;
    cin>>n>>m;
    gr.resize(n);
    for(int i =0 ;i<m;i++)
    {
        int u,v,c,d;
        cin>>u>>v>>c>>d;
        u--;v--;
        gr[u].push_back({v,c,d});
    }
    ll tans = infl;
    for(int i = 0;i<n;i++)
    {
        for(int j = 0;j<gr[i].size();j++)
        {
            vector<ll> cu = gr[i][j];
            gr[i][j][1] = infl;
            gr[gr[i][j][0]].push_back({i,cu[1],cu[2] });
            ans = gr[i][j][2];
            pq.push({0,0,0});
            pq.push({0,n-1,1});
            for(int q = 0;q<n;q++)
            {
                co[q][0] = infl;
                co[q][1] = infl;
            }
            co[0][0] = 0;
            co[n-1][1] = 0;
            while(!pq.empty())
            {
                ll b =pq.top()[0];
                int a = pq.top()[1];
                int t = pq.top()[2];
                pq.pop();
                if(b == co[a][t]) dk(a,b,t);
            }
            //cout<<co[n-1][0]<<" "<<co[0][1]<<"\n";
            ans+= co[n-1][0];
            ans += co[0][1];
            tans = min(tans,ans);
            gr[cu[0]].pop_back();
            gr[i][j][1] = cu[1];
        }
    }
    ans = 0;
    pq.push({0,0,0});
    pq.push({0,n-1 ,1});
    for(int q = 0;q<n;q++)
    {
        co[q][0] = infl;
        co[q][1] = infl;
    }
    co[0][0] = 0;
    co[n-1][1] = 0;
    while(!pq.empty())
    {
        ll b =pq.top()[0];
        int a = pq.top()[1];
        int t = pq.top()[2];
        pq.pop();
        if(b == co[a][t]) dk(a,b,t);
    }
    ans+= co[n-1][0];
    ans += co[0][1];
    //cout<<co[n-1][0]<<" "<<co[0][1]<<"\n";
    tans = min(tans,ans);
    if(tans >= 1e18)
    {
        cout<<-1;
    }
    else
    {
        cout<<tans;
    }
}

• Subtask 1: 5 / 5
• Subtask 2: 0 / 11
• Subtask 3: 0 / 21
• Subtask 4: 0 / 63