oj.uz

답안 #569803

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
569803 2022-05-27T20:13:46 Z Ronin13 Olympic Bus (JOI20_ho_t4) C++14
0 / 100
 356 ms 10240 KB 
#include<bits/stdc++.h>
#define ll long long
#define ull unsigned ll
#define f first
#define s second
#define pii pair<int,int>
#define pll pair<ll,ll>
#define pb push_back
#define epb emplace_back
using namespace std;

const ll linf = 1e18 + 1;
const int NMAX = 201;
vector <pll> vec[NMAX][NMAX];
map<pair<pii, pll>, bool> used;

bool comp1(pll a, pll b){
    return a.f < b.f;
}

bool comp2(pll a, pll b){
    return a.f + a.s < b.f + b.s;
}

bool comp3(pll a, pll b){
    return 2 * a.f + a.s < 2 * b.f + b.s;
}

vector <pair<ll, pll> > g[NMAX][2];

ll d[NMAX][NMAX][4];

void dijk(int a, int b, int ind, int bb){
    d[a][b][ind] = 0;
    if(a == b) return;
    set <pll> q;
    q.insert({d[a][b][ind], a});
    while(!q.empty()){
        int v = q.begin()->s;
        q.erase(q.begin());
        for(auto x : g[v][bb]){
            int to = x.f;
            if(to == b) continue;
            ll len = x.s.f;
            if(d[to][b][ind] > d[v][b][ind] + len){
                q.erase({d[to][b][ind], to});
                d[to][b][ind] = d[v][b][ind] + len;
                q.insert({d[to][b][ind], to});
            }
        }
    }
}
int n;

ll get(int v, int ind){
    ll x = d[n][v][0];
    ll y = d[1][v][1];
    ll mn1, mn2;
    mn1 = d[v][v][3];
    mn2 = d[v][v][0];
    for(int i = 0; i < g[v][0].size(); i++){
        if(i == ind) continue;
        int xx = g[v][0][i].f;
        ll  len = g[v][0][i].s.f;
        mn1 = min(mn1, d[xx][v][3] + len);
    }
    for(int i = 0; i < g[v][1].size(); i++){
        int xx = g[v][1][i].f;
        ll len = g[v][1][i].s.f;
        mn2 = min(mn2, d[xx][v][0] + len);
    }
    if(ind != g[v][0].size()){
        int xx = g[v][0][ind].f;
        ll len = g[v][0][ind].s.f + g[v][0][ind].s.s;
        mn2 = min(mn2, d[xx][v][0] + len);
    }
    x = min(x, mn1 + mn2);
    mn1 = d[v][v][2];
    mn2 = d[v][v][1];
    for(int i = 0; i < g[v][0].size(); i++){
        if(i == ind) continue;
        int xx = g[v][0][i].f;
        ll len = g[v][0][i].s.f;
        mn1 = min(mn1, d[xx][v][2] + len);
    }
    for(int i = 0; i < g[v][1].size(); i++){
        int xx = g[v][1][i].f;
        ll len = g[v][1][i].s.f;
        mn2 = min(mn2, d[xx][v][1] + len);
    }
    if(ind != g[v][0].size()){
        int xx = g[v][0][ind].f;
        ll len = g[v][0][ind].s.f + g[v][0][ind].s.s;
        mn2 = min(mn2, d[xx][v][1] + len);
    }
    y = min(mn1 + mn2, y);
    return x + y;
}


int main(){
    //ios_base::sync_with_stdio(false); cin.tie(0);
    int  m; cin >> n >> m;
    for(int i = 1; i <= m; i++){
        int u, v;
        ll c, d; cin >> u >> v >> c >> d;
        vec[u][v].pb({c, d});
    }
    //cout << 1;
    for(int i = 1; i <= n; i++){
        for(int j = 1; j <= n; j++){
            if(vec[i][j].empty()) continue;
            sort(vec[i][j].begin(), vec[i][j].end(), comp1);
            g[i][0].pb({j, vec[i][j][0]});
            used[{{i, j}, vec[i][j][0]}] = true;
            sort(vec[i][j].begin(), vec[i][j].end(), comp2);
            if(!used[{{i, j},vec[i][j][0]}])
            g[i][0].pb({j, vec[i][j][0]}), used[{{i, j}, vec[i][j][0]}] = true;;
            sort(vec[i][j].begin(), vec[i][j].end(), comp3);
            if(!used[{{i, j},vec[i][j][0]}])
            g[i][0].pb({j, vec[i][j][0]}), used[{{i, j}, vec[i][j][0]}] = true;;
        }
    }
   // cout << 1;
    for(int i = 1; i <= n; i++){
        for(int j = 1; j <= n; j++){
            for(int k  = 0; k < 4; k++){
                d[i][j][k] = linf;
            }

        }
    }
    for(int i = 1; i <= n; i++){
        for(auto to : g[i][0]){
            int x = to.f;
            pll v = to.s;
            g[x][1].pb({i, v});
        }
    }
    //cout << 1;
    for(int i = 1; i <= n; i++){
        dijk(1, i, 0, 0);
        dijk(n, i, 1, 0);
        dijk(1, i, 2, 1);
        dijk(n, i, 3, 1);
    }
    //cout << 1;
    ll ans = linf;
    for(int i = n; i >= 1; i--){
        for(int j = 0; j < g[i][0].size(); j++){
            //cout << i << ' ' << g[i][0][j].f << ' ' << get(i, j) << "\n";
            ans = min(ans, get(i, j));
        }

    }
    if(ans == linf) cout << -1 << "\n";
    else cout << ans;
    return 0;
}

Compilation message

ho_t4.cpp: In function 'long long int get(int, int)':
ho_t4.cpp:61:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<long long int, std::pair<long long int, long long int> > >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   61 |     for(int i = 0; i < g[v][0].size(); i++){
      |                    ~~^~~~~~~~~~~~~~~~
ho_t4.cpp:67:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<long long int, std::pair<long long int, long long int> > >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   67 |     for(int i = 0; i < g[v][1].size(); i++){
      |                    ~~^~~~~~~~~~~~~~~~
ho_t4.cpp:72:12: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<long long int, std::pair<long long int, long long int> > >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   72 |     if(ind != g[v][0].size()){
      |        ~~~~^~~~~~~~~~~~~~~~~
ho_t4.cpp:80:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<long long int, std::pair<long long int, long long int> > >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   80 |     for(int i = 0; i < g[v][0].size(); i++){
      |                    ~~^~~~~~~~~~~~~~~~
ho_t4.cpp:86:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<long long int, std::pair<long long int, long long int> > >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   86 |     for(int i = 0; i < g[v][1].size(); i++){
      |                    ~~^~~~~~~~~~~~~~~~
ho_t4.cpp:91:12: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<long long int, std::pair<long long int, long long int> > >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   91 |     if(ind != g[v][0].size()){
      |        ~~~~^~~~~~~~~~~~~~~~~
ho_t4.cpp: In function 'int main()':
ho_t4.cpp:150:26: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<long long int, std::pair<long long int, long long int> > >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  150 |         for(int j = 0; j < g[i][0].size(); j++){
      |                        ~~^~~~~~~~~~~~~~~~

Subtask #1
0 / 5.0

# 결과 실행 시간 메모리 Grader output
1 Correct 25 ms 2644 KB Output is correct
2 Correct 3 ms 2516 KB Output is correct
3 Correct 44 ms 2704 KB Output is correct
4 Correct 45 ms 2728 KB Output is correct
5 Correct 4 ms 1492 KB Output is correct
6 Correct 5 ms 2516 KB Output is correct
7 Correct 1 ms 1236 KB Output is correct
8 Correct 1 ms 1236 KB Output is correct
9 Correct 2 ms 1276 KB Output is correct
10 Correct 54 ms 2684 KB Output is correct
11 Correct 54 ms 2712 KB Output is correct
12 Correct 53 ms 2708 KB Output is correct
13 Incorrect 16 ms 2644 KB Output isn't correct
14 Halted 0 ms 0 KB -

Subtask #2
0 / 11.0

# 결과 실행 시간 메모리 Grader output
1 Correct 356 ms 9316 KB Output is correct
2 Correct 320 ms 9144 KB Output is correct
3 Correct 329 ms 9592 KB Output is correct
4 Correct 47 ms 2812 KB Output is correct
5 Correct 30 ms 2668 KB Output is correct
6 Correct 7 ms 2616 KB Output is correct
7 Correct 4 ms 2476 KB Output is correct
8 Incorrect 1 ms 1236 KB Output isn't correct
9 Halted 0 ms 0 KB -

Subtask #3
0 / 21.0

# 결과 실행 시간 메모리 Grader output
1 Correct 29 ms 2644 KB Output is correct
2 Correct 7 ms 2516 KB Output is correct
3 Correct 197 ms 9348 KB Output is correct
4 Correct 5 ms 2580 KB Output is correct
5 Correct 234 ms 10240 KB Output is correct
6 Correct 1 ms 1236 KB Output is correct
7 Correct 1 ms 1236 KB Output is correct
8 Incorrect 178 ms 9196 KB Output isn't correct
9 Halted 0 ms 0 KB -

Subtask #4
0 / 63.0

# 결과 실행 시간 메모리 Grader output
1 Correct 25 ms 2644 KB Output is correct
2 Correct 3 ms 2516 KB Output is correct
3 Correct 44 ms 2704 KB Output is correct
4 Correct 45 ms 2728 KB Output is correct
5 Correct 4 ms 1492 KB Output is correct
6 Correct 5 ms 2516 KB Output is correct
7 Correct 1 ms 1236 KB Output is correct
8 Correct 1 ms 1236 KB Output is correct
9 Correct 2 ms 1276 KB Output is correct
10 Correct 54 ms 2684 KB Output is correct
11 Correct 54 ms 2712 KB Output is correct
12 Correct 53 ms 2708 KB Output is correct
13 Incorrect 16 ms 2644 KB Output isn't correct
14 Halted 0 ms 0 KB -