제출 #641805

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
641805		danikoynov	Olympic Bus (JOI20_ho_t4)	C++14	100 / 100	359 ms	3660 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;
    ll c, d;
} e[maxm];


int n, m, used[maxn], cap[maxn][maxn];
ll dp[maxn][maxn], path[maxn][maxn], id[maxn][maxn];
ll dist[maxn], fr[maxn], sp[maxm];

void dijkstra(int v)
{
    for (int i = 1; i <= n; i ++)
        dist[i] = inf, used[i] = 0, fr[i] = -1;

    for (int i = 1; i <= n; i ++)
        for (int j = 1; j <= n; j ++)
        {
            if (i != j)
                path[i][j] = inf;
        }

    for (int j = 1; j <= m; j ++)
    {
        if (e[j].c < path[e[j].v][e[j].u])
        {
            path[e[j].v][e[j].u] = e[j].c;
            id[e[j].v][e[j].u] = j;
        }
        ///path[e[j].v][e[j].u] = min(path[e[j].v][e[j].u], e[j].c);
    }

    int cur = v;
    dist[cur] = 0;
    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] + path[cur][i] < dist[i])
            {
                dist[i] = dist[cur] + path[cur][i];
                fr[i] = id[cur][i];
            }
        }
    }
}
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;
        dp[e[i].v][e[i].u] = min(dp[e[i].v][e[i].u], (ll)e[i].c);
    }
    /**if (m <= 1000)
    {
        ll ans = 0;
        dijkstra(1);
        ans += dist[n];
        dijkstra(n);
        ans += dist[1];

        for (int i = 1; i <= m; i ++)
        {
            swap(e[i].v, e[i].u);
            ll cur = e[i].d;
            dijkstra(1);
            cur += dist[n];
            ///cout << dist[n] << endl;
            dijkstra(n);
            cur += dist[1];
            ///cout << dist[1] << endl;
            ans = min(ans, cur);
            ///cout << i << " " << cur << endl;
            swap(e[i].v, e[i].u);

        }
        if (ans <= inf)
        cout << ans << endl;
        else
            cout << -1 << endl;
        return;
    }*/


    ll ans = 0;
    dijkstra(1);
    ans += dist[n];
    if (fr[n] != -1)
    {
        int st = n;
        while(fr[st] != -1)
        {
            sp[fr[st]] = 1;
            st = e[fr[st]].v;
        }
    }
    dijkstra(n);
    ans += dist[1];
    if (fr[1] != -1)
    {
        int st = 1;
        while(fr[st] != -1)
        {
            sp[fr[st]] = 1;
            st = e[fr[st]].v;
        }
    }

    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];
            }


    for (int i = 1; i <= m; i ++)
    {
        if (sp[i])
        {
            swap(e[i].v, e[i].u);
            ll cur = e[i].d;
            dijkstra(1);
            cur += dist[n];
            ///cout << dist[n] << endl;
            dijkstra(n);
            cur += dist[1];
            ///cout << dist[1] << endl;
            ans = min(ans, cur);
            ///cout << i << " " << cur << endl;
            swap(e[i].v, e[i].u);

            continue;
        }
        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
*/

컴파일 시 표준 에러 (stderr) 메시지

ho_t4.cpp: In function 'void solve()':
ho_t4.cpp:92:10: warning: unused variable 'czero' [-Wunused-variable]
   92 |     bool czero = true;
      |          ^~~~~

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