oj.uz

답안 #245480

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
245480 2020-07-06T14:05:15 Z egekabas Olympic Bus (JOI20_ho_t4) C++14
0 / 100
 1000 ms 13336 KB 
#include <bits/stdc++.h>
#define ff first
#define ss second
#define pb push_back
#define mp make_pair
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef long double ld;
typedef pair<ll, ll>    pll;
typedef pair<ull, ull>    pull;
typedef pair<int, int>  pii;
typedef pair<ld, ld>  pld;
const ll inf = 1e18;
struct edge{
    ll x, y, z, d, id;
};
edge e[50009];
ll n, m;
ll dis[2009][2009];
vector<edge> g[2009];
void calcdepth(ll beg, ll depth[]){
    queue<ll> q;
    q.push(beg);
    for(ll i = 1; i <= n; ++i)
        depth[i] = inf;
    depth[beg] = 0;
    while(q.size()){
        ll v = q.front();
        q.pop();
        for(edge u : g[v])
            if(dis[u.x][beg] == dis[v][beg] + u.z && depth[u.x] == inf){
                depth[u.x] = depth[v]+1;
                q.push(u.x);
            }
    }
        
}
ll d1[2009];
ll dn[2009];
int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(0);cout.tie(0);

    //freopen("in.txt", "r", stdin);                                                                                             
    //freopen("out.txt", "w", stdout);
    cin >> n >> m;
    for(ll i = 1; i <= n; ++i)
        for(ll j = 1; j <= n; ++j)
            if(i != j) dis[i][j] = inf;
    for(ll i = 0; i < m; ++i){
        cin >> e[i].x >> e[i].y >> e[i].z >> e[i].d;
        e[i].id = i;
        dis[e[i].x][e[i].y] = min(dis[e[i].x][e[i].y], e[i].z);
        g[e[i].y].pb(e[i]);
    }
    for(ll k = 1; k <= n; ++k)
        for(ll i = 1; i <= n; ++i)
            for(ll j = 1; j <= n; ++j)
                dis[i][j] = min(dis[i][j], dis[i][k]+dis[k][j]);
    calcdepth(1, d1);
    calcdepth(n, dn);
    ll ans = dis[1][n]+dis[n][1];
    for(ll i = 0; i < m; ++i){
        edge u = e[i];
        ll cur = e[i].d;
        if(dn[u.y]+1 == dn[u.x]){
            cur += min(dis[n][1], dis[n][u.x]+u.z+dis[u.y][1]);
            ll di = inf;
            for(ll j = 1; j <= n; ++j)
                if(dn[j] == dn[u.y])
                    for(auto u : g[j])
                        if(u.id != i)
                            di = min(di, dis[1][u.x]+u.z+dis[u.z][n]);
            if(dn[1] <= dn[u.y])
                di = dis[1][n];
            cur += di;
        }
        else if(d1[u.y]+1 == d1[u.x]){
            cur += min(dis[1][n], dis[1][u.x]+u.z+dis[u.y][n]);
            ll di = inf;
            for(ll j = 1; j <= n; ++j)
                if(d1[j] == d1[u.y])
                    for(auto u : g[j])
                        if(u.id != i)
                            di = min(di, dis[n][u.x]+u.z+dis[u.z][1]);
            if(d1[n] <= d1[u.y])
                di = dis[n][1];
            cur += di;
        }
        else{
            cur += min(dis[1][n], dis[1][u.y]+u.z+dis[u.x][n]);
            cur += min(dis[n][1], dis[n][u.y]+u.z+dis[u.x][1]);
        }
        ans = min(ans, cur);
    }
    if(ans >= inf)
        cout << -1;
    else
        cout << ans;
}

Subtask #1
0 / 5.0

# 결과 실행 시간 메모리 Grader output
1 Correct 17 ms 1664 KB Output is correct
2 Correct 15 ms 1536 KB Output is correct
3 Runtime error 20 ms 3200 KB Execution killed with signal 11 (could be triggered by violating memory limits)
4 Halted 0 ms 0 KB -

Subtask #2
0 / 11.0

# 결과 실행 시간 메모리 Grader output
1 Runtime error 47 ms 13336 KB Execution killed with signal 11 (could be triggered by violating memory limits)
2 Halted 0 ms 0 KB -

Subtask #3
0 / 21.0

# 결과 실행 시간 메모리 Grader output
1 Correct 15 ms 1664 KB Output is correct
2 Correct 14 ms 1528 KB Output is correct
3 Correct 776 ms 5596 KB Output is correct
4 Correct 15 ms 1536 KB Output is correct
5 Execution timed out 1099 ms 6776 KB Time limit exceeded
6 Halted 0 ms 0 KB -

Subtask #4
0 / 63.0

# 결과 실행 시간 메모리 Grader output
1 Correct 17 ms 1664 KB Output is correct
2 Correct 15 ms 1536 KB Output is correct
3 Runtime error 20 ms 3200 KB Execution killed with signal 11 (could be triggered by violating memory limits)
4 Halted 0 ms 0 KB -