Submission #227162

#	Time	Username	Problem	Language	Result	Execution time	Memory
227162		ho94949	Olympic Bus (JOI20_ho_t4)	C++17	100 / 100	327 ms	2552 KiB

ho_t4

#include <bits/stdc++.h>
using namespace std;

const int MAXN = 200, MAXM = 50'000, INF = 0x3f3f3f3f;

int N, M;
int U[MAXM], V[MAXM], C[MAXM], D[MAXM];
bool issp[MAXM]; // is vertex contained in shortest path DAG? ((1, N) -> x, (1, N) <- x)

int adj[MAXN][MAXN]; int from[MAXN]; bool vis[MAXN];

int dis0[MAXN], dis0r[MAXN], disN[MAXN], disNr[MAXN], dis[MAXN];

int dijk(int s, int e)
{
    memset(dis, 0x3f, sizeof dis);
    memset(vis, 0, sizeof vis);
    dis[s] = 0;
    for(int iter = 0; iter<N; ++iter)
    {
        int minv = INF, mini = -1;
        for(int i=0; i<N; ++i) if(!vis[i])
            if(minv > dis[i])
            {
                minv = dis[i];
                mini = i;
            }
        if(mini == -1) break;
        if(mini == e) return minv;
        vis[mini] = true;
        for(int i=0; i<N; ++i) if(!vis[i])
            if(dis[i] > dis[mini] + adj[mini][i])
                dis[i] = dis[mini] + adj[mini][i];
    }
    return INF;
}

int exc(int e)
{
    memset(adj, 0x3f, sizeof adj);
    for(int i=0; i<M; ++i)
    {
        int u = U[i], v = V[i], c = C[i];
        if(i==e) swap(u, v);
        adj[u][v] = min(adj[u][v], c);
    }
    return dijk(0, N-1) + dijk(N-1, 0);
}

void SP(int s, int* S, int *E, int *dis)
{
    memset(adj, -1, sizeof adj);
    memset(dis, 0x3f, sizeof(int)*N);
    memset(vis, 0, sizeof vis);

    for(int i=0; i<M; ++i)
    {
        int u = S[i], v = E[i];
        if(adj[u][v] == -1 || C[adj[u][v]] > C[i])
            adj[u][v] = i;
    }
    dis[s] = 0;
    for(int iter=0; iter<N; ++iter)
    {
        int minv = INF, mini = -1;
        for(int i=0; i<N; ++i) if(!vis[i])
            if(dis[i] < minv)
                minv = dis[i], mini = i;
        if(mini == -1) break;


        vis[mini] = true;
        issp[from[mini]] = true;

        for(int i=0; i<N; ++i)
            if(!vis[i] && adj[mini][i]!=-1)
            {
                int e = adj[mini][i];
                if(dis[i] > dis[mini] + C[e])
                {
                    dis[i] = dis[mini] + C[e];
                    from[i] = e;
                }
            }
    }

}

int main()
{
    scanf("%d%d", &N, &M);
    for(int i=0; i<M; ++i)
    {
        scanf("%d%d%d%d", U+i, V+i, C+i, D+i);
        --U[i]; --V[i];
    }
    SP(0, U, V, dis0); SP(0, V, U, dis0r);
    SP(N-1, U, V, disN); SP(N-1, V, U, disNr);
    
    long long ans = dis0[N-1] + disN[0];
    for(int i=0; i<M; ++i)
    {
        long long ret = D[i];
        long long u = U[i], v = V[i], c = C[i];
        if(issp[i]) ret += exc(i);
        else
        {
            ret += min((long long) dis0[N-1], dis0[v] + c + disNr[u]);
            ret += min((long long) disN[0], disN[v] + c + dis0r[u]);
        }
        ans = min(ans, ret);
    }
    if(ans >= INF) ans = -1;
    printf("%lld\n", ans);
}

Compilation message (stderr)

ho_t4.cpp: In function 'int main()':
ho_t4.cpp:91: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:94: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, D+i);
         ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

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