oj.uz

Submission #224208

# Submission time Handle Problem Language Result Execution time Memory
224208 2020-04-17T13:11:15 Z lyc Olympic Bus (JOI20_ho_t4) C++14
0 / 100
 1000 ms 2688 KB 
#include <bits/stdc++.h>
using namespace std;

#define TRACE(x) cerr << #x << " :: " << x << endl
#define _ << " " <<
#define SZ(x) (int)(x).size()
#define FOR(i,a,b) for(int i=(a);i<=(b);++i)
#define RFOR(i,a,b) for (int i=(a);i>=(b);--i)

const int MX_N = 205;
const int MX_M = 5e4+5;

const int INF = 1e9;

struct Edge { int v, c, d, i; };

int N, M;
vector<Edge> al[MX_N];
int dist[2][MX_N];

void dijkstra(int s, vector<Edge>* al, int* dist, int blocked) {
    fill(dist+1,dist+1+N,INF);
    dist[s] = 0;
    bool done[N+1];
    fill(done+1,done+1+N,0);
    while (true) {
        int u = -1;
        FOR(v,1,N) if (!done[v] && (u == -1 || dist[v] < dist[u])) u = v;
        if (u == -1) break;
        done[u] = 1;
        for (auto e : al[u]) if (e.i != blocked) {
            if (dist[u] + e.c < dist[e.v]) {
                dist[e.v] = dist[u] + e.c;
            }
        }
    }
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);

    cin >> N >> M;
    FOR(i,1,M){
        int U, V, C, D; cin >> U >> V >> C >> D;
        al[U].push_back({V,C,D,i});
    }

    dijkstra(1,al,dist[0],-1);
    dijkstra(N,al,dist[1],-1);
    int ans = min(INF, dist[0][N] + dist[1][1]);
    FOR(u,1,N){
        for (auto& e : al[u]) {
            al[e.v].push_back({u,e.c,e.d,M+1});
            dijkstra(1,al,dist[0],e.i);
            dijkstra(N,al,dist[1],e.i);
            al[e.v].pop_back();
            ans = min(ans, dist[0][N] + dist[1][1] + e.d);
        }
    }

    cout << (ans == INF ? -1 : ans) << '\n';
}

Subtask #1
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 184 ms 384 KB Output is correct
2 Incorrect 47 ms 384 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #2
0 / 11.0

# Verdict Execution time Memory Grader output
1 Execution timed out 1093 ms 2688 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #3
0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 188 ms 504 KB Output is correct
2 Incorrect 47 ms 384 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #4
0 / 63.0

# Verdict Execution time Memory Grader output
1 Correct 184 ms 384 KB Output is correct
2 Incorrect 47 ms 384 KB Output isn't correct
3 Halted 0 ms 0 KB -