제출 #641733

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
641733		danikoynov	Olympic Bus (JOI20_ho_t4)	C++14	32 / 100	79 ms	2896 KiB

ho_t4

/**
 ____ ____ ____ ____ ____ ____
||l |||e |||i |||n |||a |||d ||
||__|||__|||__|||__|||__|||__||
|/__\|/__\|/__\|/__\|/__\|/__\|

**/

#include<bits/stdc++.h>
#define endl '\n'

using namespace std;
typedef long long ll;

void speed()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
}

const int maxn = 210, maxm = 50010;
const ll inf = 1e17;
struct edge
{
    int v, u, c, d;
} e[maxm];

bool cmp_d(edge e1, edge e2)
{
    return e1.d < e2.d;
}

int n, m, used[maxn], path[maxn][maxn], cap[maxn][maxn];
ll dp[maxn][maxn];
ll dist[maxn];
void dijkstra(int v)
{
    for (int i = 1; i <= n; i ++)
        dist[i] = inf, used[i] = 0;

    int cur = v;
    dist[cur] = 0;
    used[cur] = 1;
    while(true)
    {
        int mx = -1;
        for (int i = 1; i <= n; i ++)
        {
            if (!used[i] && (mx == -1 || dist[i] < dist[mx]))
                mx = i;
        }

        if (mx == -1)
            break;

        cur = mx;
        used[cur] = 1;
        for (int i = 1; i <= n; i ++)
        {
            if (!used[i] && dist[cur] + dp[i][cur] < dist[i])
            {
                dist[i] = dist[cur] + dp[i][cur];
            }
        }
    }
}
void solve()
{
    cin >> n >> m;
    for (int i = 1; i <= n; i ++)
        for (int j = 1; j <= n; j ++)
    {
        if (i != j)
            dp[i][j] = inf;
    }


    bool czero = true;
    for (int i = 1; i <= m; i ++)
    {
        cin >> e[i].v >> e[i].u >> e[i].c >> e[i].d;
        path[e[i].v][e[i].u] = 1;
        dp[e[i].v][e[i].u] = min(dp[e[i].v][e[i].u], (ll)e[i].c);
        cap[e[i].v][e[i].u] ++;
        if (e[i].c != 0)
            czero = false;
    }
    /**if (m <= 1000)
    {
        for (int i = 1; i <= m; i ++)
        {
            int v = e[i].v,
        }
        return;
    }*/
    if (czero)
    {
        sort(e + 1, e + m + 1, cmp_d);

        for (int i = 1; i <= n; i ++)
            path[i][i] = 1;
        for (int k = 1; k <= n; k ++)
            for (int i = 1; i <= n; i ++)
                for (int j = 1; j <= n; j ++)
                {
                    if (path[i][k] == 1 && path[k][j] == 1)
                    {
                        ///cout << i << " " << k << " " << j << endl;
                        path[i][j] = 1;
                    }
                }

        if (path[1][n] == 1 && path[n][1] == 1)
        {
            cout << 0 << endl;
            return;
        }

        if (path[1][n] == 0 && path[n][1] == 0)
        {
            bool tf = false;
            for (int i = 1; i <= m; i ++)
            {
                int v = e[i].v, u = e[i].u;
                ///cout << v << " " << u << endl;
                ///cout << path[1][u] << " " << path[v][n] << " " << path[n][u] << " " << path[v][1] << endl;
                if (path[1][u] == 1 && path[v][n] == 1 &&
                        path[n][u] == 1 && path[v][1] == 1)
                {
                    cout << e[i].d << endl;
                    tf = true;
                    break;
                }
            }
            if (!tf)
            {
                cout << -1 << endl;
            }
            return;
        }

        if (path[1][n] == 0)
        {
            bool tf = false;
            for (int i = 1; i <= m; i ++)
            {
                int v = e[i].v, u = e[i].u;
                if (path[1][u] == 1 && path[v][n] == 1)
                {
                    cap[v][u] --;
                    cap[u][v] ++;

                    for (int j = 1; j <= n; j ++)
                        used[j] = 0;
                    queue < int > q;
                    q.push(n);
                    used[n] = 1;
                    while(!q.empty())
                    {
                        int cur = q.front();
                        q.pop();
                        for (int j = 1; j <= n; j ++)
                            if (cap[cur][j] > 0 && !used[j])
                            {
                                used[j] = 1;
                                q.push(j);
                            }
                    }
                    if (used[1] == 1)
                    {
                        cout << e[i].d << endl;
                        tf = true;
                        break;
                    }
                    cap[v][u] ++;
                    cap[u][v] --;
                }
            }
            if (!tf)
            {
                cout << -1 << endl;
            }
            return;

        }

        if (path[n][1] == 0)
        {
            bool tf = false;
            for (int i = 1; i <= m; i ++)
            {
                int v = e[i].v, u = e[i].u;
                if (path[n][u] == 1 && path[v][1] == 1)
                {
                    cap[v][u] --;
                    cap[u][v] ++;

                    for (int j = 1; j <= n; j ++)
                        used[j] = 0;
                    queue < int > q;
                    q.push(1);
                    used[1] = 1;
                    while(!q.empty())
                    {
                        int cur = q.front();
                        q.pop();
                        for (int j = 1; j <= n; j ++)
                            if (cap[cur][j] > 0 && !used[j])
                            {
                                used[j] = 1;
                                q.push(j);
                            }
                    }
                    if (used[n] == 1)
                    {
                        cout << e[i].d << endl;
                        tf = true;
                        break;
                    }
                    cap[v][u] ++;
                    cap[u][v] --;
                }
            }
            if (!tf)
            {
                cout << -1 << endl;
            }
            return;
        }

    }
    else
    {
        for (int k = 1; k <= n; k ++)
            for (int i = 1; i <= n; i ++)
            for (int j = 1; j <= n; j ++)
        {
            if (dp[i][k] + dp[k][j] < dp[i][j])
                dp[i][j] = dp[i][k] + dp[k][j];
        }

        ll ans = dp[1][n] + dp[n][1];
        for (int i = 1; i <= m; i ++)
        {
            int v = e[i].v, u = e[i].u;

            ll cur = min(dp[1][u] + dp[v][n] + e[i].c, dp[1][n]) + min(dp[n][u] + dp[v][1] + e[i].c, dp[n][1]) + e[i].d;
             ///if (e[i].d < 74779 && e[i].c < 74779 && dp[v][1] < 74779)
            ///cout << cur << " " << e[i].d << " " << e[i].c << " " << dp[n][u] << " " << dp[v][1] << endl;
            if (cur < ans)
                ans = cur;
        }

        if (ans < inf)
        cout << ans << endl;
        else
            cout << -1 << endl;
    }

}

int main()
{
    ///freopen("test.txt", "r", stdin);
    solve();
    return 0;
}

/**
4 4
2 1 0 4
3 1 0 1
3 4 0 2
1 4 0 1
*/

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