제출 #569803

#제출 시각아이디문제언어결과실행 시간메모리
569803Ronin13Olympic Bus (JOI20_ho_t4)C++14
0 / 100
356 ms10240 KiB
#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++){
      |                        ~~^~~~~~~~~~~~~~~~
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...