제출 #569803

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
569803		Ronin13	Olympic Bus (JOI20_ho_t4)	C++14	0 / 100	356 ms	10240 KiB

ho_t4

#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;
}

컴파일 시 표준 에러 (stderr) 메시지

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
• Subtask 2: 0 / 11
• Subtask 3: 0 / 21
• Subtask 4: 0 / 63