oj.uz

답안 #224209

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
224209 2020-04-17T13:16:11 Z lyc Olympic Bus (JOI20_ho_t4) C++14
5 / 100
 1000 ms 1920 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 long long INF = 1e18;

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

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

void dijkstra(int s, vector<Edge>* al, long long* 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);
    long long ans = min(INF, (long long) 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, (long long) dist[0][N] + dist[1][1] + e.d);
        }
    }

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

Subtask #1
5.0 / 5.0

# 결과 실행 시간 메모리 Grader output
1 Correct 204 ms 504 KB Output is correct
2 Correct 52 ms 384 KB Output is correct
3 Correct 211 ms 384 KB Output is correct
4 Correct 217 ms 504 KB Output is correct
5 Correct 15 ms 384 KB Output is correct
6 Correct 51 ms 512 KB Output is correct
7 Correct 5 ms 384 KB Output is correct
8 Correct 5 ms 384 KB Output is correct
9 Correct 8 ms 384 KB Output is correct
10 Correct 216 ms 384 KB Output is correct
11 Correct 213 ms 376 KB Output is correct
12 Correct 215 ms 504 KB Output is correct
13 Correct 214 ms 384 KB Output is correct
14 Correct 203 ms 504 KB Output is correct
15 Correct 205 ms 384 KB Output is correct
16 Correct 200 ms 456 KB Output is correct

Subtask #2
0 / 11.0

# 결과 실행 시간 메모리 Grader output
1 Execution timed out 1083 ms 1784 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #3
0 / 21.0

# 결과 실행 시간 메모리 Grader output
1 Correct 209 ms 504 KB Output is correct
2 Correct 50 ms 384 KB Output is correct
3 Execution timed out 1091 ms 1920 KB Time limit exceeded
4 Halted 0 ms 0 KB -

Subtask #4
0 / 63.0

# 결과 실행 시간 메모리 Grader output
1 Correct 204 ms 504 KB Output is correct
2 Correct 52 ms 384 KB Output is correct
3 Correct 211 ms 384 KB Output is correct
4 Correct 217 ms 504 KB Output is correct
5 Correct 15 ms 384 KB Output is correct
6 Correct 51 ms 512 KB Output is correct
7 Correct 5 ms 384 KB Output is correct
8 Correct 5 ms 384 KB Output is correct
9 Correct 8 ms 384 KB Output is correct
10 Correct 216 ms 384 KB Output is correct
11 Correct 213 ms 376 KB Output is correct
12 Correct 215 ms 504 KB Output is correct
13 Correct 214 ms 384 KB Output is correct
14 Correct 203 ms 504 KB Output is correct
15 Correct 205 ms 384 KB Output is correct
16 Correct 200 ms 456 KB Output is correct
17 Execution timed out 1083 ms 1784 KB Time limit exceeded
18 Halted 0 ms 0 KB -