Submission #896544

#	Time	Username	Problem	Language	Result	Execution time	Memory
896544		ace5	Olympic Bus (JOI20_ho_t4)	C++17	100 / 100	289 ms	5768 KiB

ho_t4

#include <bits/stdc++.h>

using namespace std;

#define int int64_t

const int maxn = 201;
const int INF = 1e18;

vector<pair<int,int>> g[maxn];
vector<int> c,d;
vector<pair<int,int>> r;
int nr[maxn][maxn];
int dp[maxn][maxn];
int rr[maxn][maxn];
vector<bool> ru;

void rec(int s,int t)
{
    if(dp[s][t] == INF)
    {
        return ;
    }
    if(rr[s][t] == -1)
    {
        ru[nr[s][t]] = 1;
        return ;
    }
    int rp = rr[s][t];
    rec(s,rp);
    rec(rp,t);
    return ;
}

signed main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    int n,m;
    cin >> n >> m;
    for(int i =0;i < n;++i)
    {
        for(int j = 0;j < n;++j)
        {
            nr[i][j] = -1;
        }
    }
    for(int i =0;i < m;++i)
    {
        int u,v,e,f;
        cin >> u >> v >> e >> f;
        u--;
        v--;
        g[u].push_back({v,i});
        c.push_back(e);
        d.push_back(f);
        r.push_back({u,v});
        if(nr[u][v] == -1 || c[nr[u][v]] > e)
        {
            nr[u][v] = i;
        }
    }
   // cout << 1;
    for(int i =0;i < n;++i)
    {
        for(int j = 0;j < n;++j)
        {
            if(i == j)
            {
                dp[i][j] = 0;
            }
            else
                dp[i][j] = (nr[i][j] == -1 ? INF : c[nr[i][j]]);
            rr[i][j] = -1;
        }
    }
  //  cout << 1;
    for(int k = 0;k < n;++k)
    {
        for(int i = 0;i < n;++i)
        {
            for(int j = 0;j < n;++j)
            {
                if(dp[i][j] > dp[i][k] + dp[k][j])
                {
                    dp[i][j] = dp[i][k] + dp[k][j];
                    rr[i][j] = k;
                }
            }
        }
    }
   // cout << 1;
    ru.resize(r.size());
    rec(0,n-1);
    rec(n-1,0);
    int64_t ans = dp[0][n-1] + dp[n-1][0];
   // cout << ans << ' ';
    for(int i = 0;i < m;++i)
    {
        if(!ru[i])
        {
            //cout << i << ' ';
            ans = min(ans,d[i] + min(dp[0][r[i].second] + c[i] + dp[r[i].first][n-1],dp[0][n-1]) + min(dp[n-1][r[i].second] + c[i] + dp[r[i].first][0],dp[n-1][0]));
        }
        else
        {
            int64_t tres = d[i];
            vector<vector<pair<int,int>>> g2(n);
            for(int j = 0;j < m;++j)
            {
                if(j != i)
                {
                    g2[r[j].first].push_back({r[j].second,c[j]});
                }
                else
                {
                    g2[r[j].second].push_back({r[j].first,c[j]});
                }
            }
            vector<int> vis(n);
            vector<int> d(n,INF);
            d[0] = 0;
            while(true)
            {
                int pm = -1;
                for(int k = 0;k < n;++k)
                {
                    if(!vis[k] && (pm == -1 || d[pm] > d[k]))
                    {
                        pm = k;
                    }
                }
                if(pm == -1 || d[pm] == INF)
                {
                    break;
                }
                vis[pm] = 1;
                for(auto [u,dd] : g2[pm])
                {
                    if(d[pm] + dd < d[u])
                    {
                        d[u] = d[pm] + dd;
                    }
                }
            }
            tres += d[n-1];
            vis.clear();
            vis.resize(n);
            d.clear();
            d.resize(n);
            for(int j = 0;j < n;++j)
            {
                d[j] = INF;
            }
            d[n-1] = 0;
            while(true)
            {
                int pm = -1;
                for(int k = 0;k < n;++k)
                {
                    if(!vis[k] && (pm == -1 || d[pm] > d[k]))
                    {
                        pm = k;
                    }
                }
                if(pm == -1 || d[pm] == INF)
                {
                    break;
                }
                vis[pm] = 1;
                for(auto [u,dd] : g2[pm])
                {
                    if(d[pm] + dd < d[u])
                    {
                        d[u] = d[pm] + dd;
                    }
                }
            }
            tres += d[0];
            ans = min(ans,tres);
        }
    }
    cout << (ans >= INF ? -1 : ans);
    return 0;
}

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