Submission #202481

#	Time	Username	Problem	Language	Result	Execution time	Memory
202481		Kastanda	Olympic Bus (JOI20_ho_t4)	C++11	100 / 100	367 ms	1912 KiB

ho_t4

// In The Name Of The Queen
#include<bits/stdc++.h>
using namespace std;
const int N = 209, M = 50004;
int n, m, U[M], V[M], C[M], DR[M], P[N];
bool MR[N], Mark[M];
long long F[N], D[N][N];
vector < int > Adj[N];
inline long long SSSP(int st, int fn, int j)
{
    memset(F, 63, sizeof(F));
    memset(MR, 0, sizeof(MR));
    F[st] = 0;
    for (int __ = 1; __ <= n; __ ++)
    {
        int v = -1;
        for (int i = 1; i <= n; i ++)
            if (!MR[i] && (v == -1 || F[v] > F[i]))
                v = i;
        MR[v] = 1;
        for (int i : Adj[v])
            if (i != j && F[V[i]] > F[v] + C[i])
                F[V[i]] = F[v] + C[i];
        if (v == V[j])
            if (F[U[j]] > F[v] + C[j])
                F[U[j]] = F[v] + C[j];
    }
    return (F[fn]);
}
inline long long Solve(int st, int fn)
{
    memset(P, 0, sizeof(P));
    memset(F, 63, sizeof(F));
    memset(MR, 0, sizeof(MR));
    memset(Mark, 0, sizeof(Mark));
    F[st] = 0;
    for (int __ = 1; __ <= n; __ ++)
    {
        int v = -1;
        for (int i = 1; i <= n; i ++)
            if (!MR[i] && (v == -1 || F[v] > F[i]))
                v = i;
        MR[v] = 1;
        for (int i : Adj[v])
            if (F[V[i]] > F[v] + C[i])
                F[V[i]] = F[v] + C[i],
                P[V[i]] = i;
    }
    long long Mn = LLONG_MAX;
    if (!P[fn])
        return (Mn);
    int v = fn;
    while (v != st)
        Mark[P[v]] = 1, v = U[P[v]];
    for (int i = 1; i <= m; i ++)
        if (!Mark[i])
            Mn = min(Mn, D[fn][V[i]] + C[i] + D[U[i]][st] + DR[i] + F[fn]);
    for (int j = 1; j <= m; j ++)
        if (Mark[j])
            Mn = min(Mn, SSSP(st, fn, j) + SSSP(fn, st, j) + DR[j]);
    return (Mn);
}
int main()
{
    scanf("%d%d", &n, &m);
    memset(D, 63, sizeof(D));
    for (int i = 1; i <= m; i ++)
    {
        scanf("%d%d%d%d", &U[i], &V[i], &C[i], &DR[i]);
        D[U[i]][V[i]] = min(D[U[i]][V[i]], 1LL * C[i]);
        Adj[U[i]].push_back(i);
    }
    for (int i = 1; i <= n; i ++)
        D[i][i] = 0;
    for (int k = 1; k <= n; k ++)
        for (int i = 1; i <= n; i ++)
            for (int j = 1; j <= n; j ++)
                D[i][j] = min(D[i][j], D[i][k] + D[k][j]);
    long long Mn = D[1][n] + D[n][1];
    for (int i = 1; i <= m; i ++)
        if (D[1][V[i]] + C[i] + D[U[i]][n] < D[1][n] && D[n][V[i]] + C[i] + D[U[i]][1] < D[n][1])
            Mn = min(Mn, D[1][V[i]] + C[i] + D[U[i]][n] + D[n][V[i]] + C[i] + D[U[i]][1] + DR[i]);
    Mn = min(Mn, Solve(1, n));
    Mn = min(Mn, Solve(n, 1));
    if (Mn > (long long)(1e10) * n)
        Mn = -1;
    return !printf("%lld\n", Mn);
}

Compilation message (stderr)

ho_t4.cpp: In function 'int main()':
ho_t4.cpp:65:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%d%d", &n, &m);
     ~~~~~^~~~~~~~~~~~~~~~
ho_t4.cpp:69:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         scanf("%d%d%d%d", &U[i], &V[i], &C[i], &DR[i]);
         ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

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