Submission #1172485

#	Time	Username	Problem	Language	Result	Execution time	Memory
1172485		Hanksburger	Olympic Bus (JOI20_ho_t4)	C++20	100 / 100	77 ms	10824 KiB

ho_t4

#include <bits/stdc++.h>
#define int long long
using namespace std;
vector<pair<int, pair<int, int> > > adj[205], rev[205];
int dist[205][205], d[205], final[205];
map<pair<int, int>, int> ans1, ans2;
set<pair<int, int> > edges1, edges2;
pair<int, int> pre[205][205];
signed main()
{
    //ios::sync_with_stdio(0);
    //cin.tie(0);
    //cout.tie(0);
    int n, m;
    cin >> n >> m;
    for (int i=1; i<=m; i++)
    {
        int u, v, c, d;
        cin >> u >> v >> c >> d;
        adj[u].push_back({v, {c, d}});
        rev[v].push_back({u, {c, d}});
    }
    for (int i=1; i<=n; i++)
        dist[1][i]=1e18;
    dist[1][1]=0;
    for (int i=1; i<=n; i++)
    {
        int u, mn=1e18+1;
        for (int j=1; j<=n; j++)
        {
            if (!final[j] && mn>dist[1][j])
            {
                mn=dist[1][j];
                u=j;
            }
        }
        final[u]=1;
        for (int j=0; j<adj[u].size(); j++)
        {
            int v=adj[u][j].first, w=adj[u][j].second.first;
            if (dist[1][v]>dist[1][u]+w)
            {
                dist[1][v]=dist[1][u]+w;
                pre[1][v]={u, j};
            }
        }
    }
    for (int i=1; i<=n; i++)
        dist[i][1]=1e18, final[i]=0;
    dist[1][1]=0;
    for (int i=1; i<=n; i++)
    {
        int u, mn=1e18+1;
        for (int j=1; j<=n; j++)
        {
            if (!final[j] && mn>dist[j][1])
            {
                mn=dist[j][1];
                u=j;
            }
        }
        final[u]=1;
        for (int j=0; j<rev[u].size(); j++)
        {
            int v=rev[u][j].first, w=rev[u][j].second.first;
            dist[v][1]=min(dist[v][1], dist[u][1]+w);
        }
    }
    for (int i=1; i<=n; i++)
        dist[n][i]=1e18, final[i]=0;
    dist[n][n]=0;
    for (int i=1; i<=n; i++)
    {
        int u, mn=1e18+1;
        for (int j=1; j<=n; j++)
        {
            if (!final[j] && mn>dist[n][j])
            {
                mn=dist[n][j];
                u=j;
            }
        }
        final[u]=1;
        for (int j=0; j<adj[u].size(); j++)
        {
            int v=adj[u][j].first, w=adj[u][j].second.first;
            if (dist[n][v]>dist[n][u]+w)
            {
                dist[n][v]=dist[n][u]+w;
                pre[n][v]={u, j};
            }
        }
    }
    for (int i=1; i<=n; i++)
        dist[i][n]=1e18, final[i]=0;
    dist[n][n]=0;
    for (int i=1; i<=n; i++)
    {
        int u, mn=1e18+1;
        for (int j=1; j<=n; j++)
        {
            if (!final[j] && mn>dist[j][n])
            {
                mn=dist[j][n];
                u=j;
            }
        }
        final[u]=1;
        for (int j=0; j<rev[u].size(); j++)
        {
            int v=rev[u][j].first, w=rev[u][j].second.first;
            dist[v][n]=min(dist[v][n], dist[u][n]+w);
        }
    }
    if (dist[1][n]<1e14)
    {
        int cur=n;
        while (cur!=1)
        {
            edges1.insert(pre[1][cur]);
            cur=pre[1][cur].first;
        }
    }
    if (dist[n][1]<1e14)
    {
        int cur=1;
        while (cur!=n)
        {
            edges2.insert(pre[n][cur]);
            cur=pre[n][cur].first;
        }
    }
    for (auto edge:edges1)
    {
        for (int i=1; i<=n; i++)
            d[i]=1e18, final[i]=0;
        d[1]=0;
        for (int i=1; i<=n; i++)
        {
            int u, mn=1e18+1;
            for (int j=1; j<=n; j++)
            {
                if (!final[j] && mn>d[j])
                {
                    mn=d[j];
                    u=j;
                }
            }
            final[u]=1;
            for (int j=0; j<adj[u].size(); j++)
            {
                int v=adj[u][j].first, w=adj[u][j].second.first;
                if (edge!=make_pair(u, j))
                    d[v]=min(d[v], d[u]+w);
            }
            if (u==adj[edge.first][edge.second].first)
            {
                int v=edge.first, w=adj[edge.first][edge.second].second.first;
                d[v]=min(d[v], d[u]+w);
            }
        }
        ans1[edge]=d[n];
    }
    for (auto edge:edges2)
    {
        for (int i=1; i<=n; i++)
            d[i]=1e18, final[i]=0;
        d[n]=0;
        for (int i=1; i<=n; i++)
        {
            int u, mn=1e18+1;
            for (int j=1; j<=n; j++)
            {
                if (!final[j] && mn>d[j])
                {
                    mn=d[j];
                    u=j;
                }
            }
            final[u]=1;
            for (int j=0; j<adj[u].size(); j++)
            {
                int v=adj[u][j].first, w=adj[u][j].second.first;
                if (edge!=make_pair(u, j))
                    d[v]=min(d[v], d[u]+w);
            }
            if (u==adj[edge.first][edge.second].first)
            {
                int v=edge.first, w=adj[edge.first][edge.second].second.first;
                d[v]=min(d[v], d[u]+w);
            }
        }
        ans2[edge]=d[1];
    }
    int ans=dist[1][n]+dist[n][1];
    for (int u=1; u<=n; u++)
    {
        for (int i=0; i<adj[u].size(); i++)
        {
            int v=adj[u][i].first, w=adj[u][i].second.first, x=adj[u][i].second.second;
            if (edges1.find({u, i})==edges1.end())
                ans1[{u, i}]=min(dist[1][n], dist[1][v]+dist[u][n]+w);
            if (edges2.find({u, i})==edges2.end())
                ans2[{u, i}]=min(dist[n][1], dist[n][v]+dist[u][1]+w);
            ans=min(ans, ans1[{u, i}]+ans2[{u, i}]+x);
        }
    }
    cout << (ans>1e14?-1:ans);
}

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