제출 #724841

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

ho_t4

#include<bits/stdc++.h>
#include<fstream>
using namespace std;
ifstream fin("WINTER.inp");
ofstream fout("WINTER.out");
#define ll long long
#define int long long
#define pb push_back
#define forr(i, a, b) for(int i = a; i < b; i++)
#define dorr(i, a, b) for(int i = a; i >= b; i--)
#define ld long double
#define vt vector
#include<fstream>
#define fi first
#define se second
#define pll pair<ll, ll>
#define pii pair<int, int>
const ld PI = 3.14159265359;
const ll mod = 1e9 + 7;
const int mxn = 205, mxm = 50005;

struct ch{
    int u, type; ll dd;
};
struct E{
    int u, v, c, e;
};
int n, m;
vt<E>adj[mxn + 1], rev[mxn + 1];
E edge[mxm + 1];
bool used1[mxm + 1], vis[mxn + 1], usedn[mxm + 1];
pii trace[mxn + 1];
ll d[mxn + 1], d2[mxn + 1][2];
ll U = -1, V, W, ID = -1;
struct cmp{
    bool operator()(const ch &a, const ch &b){
        return(a.dd > b.dd);
    }
};
void D(int s){
    
    forr(i, 1, n + 1){
        d[i] = 1e18; vis[i] = false;
        trace[i] = make_pair(-1, -1);
    }
    d[s] = 0; 
    priority_queue<pll, vt<pll>, greater<pll>>pq; pq.push({d[s], s});
    while(!pq.empty()){
        auto [dd, u] = pq.top(); pq.pop();
        if(d[u] != dd)continue;
        for(auto [v, c, e, id]: adj[u]){
            if(id == ID)continue;
            if(d[v] > d[u] + c){
                d[v] = d[u] + c; trace[v] = make_pair(id, u);
                pq.push({d[v], v});
            }
        }
        if(u == U){
            if(d[V] > d[U] + W){
                d[V] = d[U] + W;
                pq.push({d[V], V});
            }
        }
    }
}
void D2(int s){
    forr(i, 1, n + 1){
        d2[i][0] = d2[i][1] = 1e18; vis[i] = false;
        
    }
    priority_queue<ch, vt<ch>, cmp>pq; d2[s][0] = 0; pq.push({s, 0, d2[s][0]});
    while(!pq.empty()){
        auto [u, type, dd] = pq.top(); pq.pop();
        if(d2[u][type] != dd)continue;
        for(auto [v, c, e, id]: adj[u]){
            
            if(d2[v][type] > d2[u][type] + c){
                d2[v][type] = d2[u][type] + c;
                pq.push({v, type, d2[v][type]});
            }
        }
        if(type == 0){
            for(auto [v, c, e, id]: rev[u]){
                if((s == 1 && usedn[id]) || (s == n && used1[id]))continue;
                if(d2[v][1] > d2[u][0] + c + e){
                    d2[v][1] = d2[u][0] + c + e;
                    pq.push({v, 1, d2[v][1]});
                }
            }
        }
    }
}
signed main(){
    
    ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
    cin >> n >> m;
    ID = -1;
    forr(i, 0, m){
        int u, v, c, e; cin >> u >> v >> c >> e;
        adj[u].pb({v, c, e, i}); rev[v].pb({u, c, e, i});
        edge[i] = {u, v, c, e};
    }
    bool ok1 = true, ok2 = true;
    
    D(1);
    
    ll dn = 1e18, d1 = 1e18;
    if(d[n]  < 1e18){
        ok1 = false;
        dn = d[n];
        int v = n;
        while(v != 1){
            used1[trace[v].fi] = 1;
            v = trace[v].se;
        }
    }
    D(n);
    if(d[1] < 1e18){
        d1 = d[1];
        ok2 = false;
        int v = 1;
        while(v != n){
            usedn[trace[v].fi] = 1;
            v = trace[v].se;
        }
    }
  
    //all edge from dijkstra Path -> o(n) Path
    ll ans = d1 + dn;
    
    if(ok1 && ok2){
        cout << -1; return(0);
    }
    if(!ok1){
        D2(n);
        
        ans = min(ans, min(d2[1][1], d2[1][0]) + dn);
    }if(!ok2){
        D2(1);
        ans = min(ans, d2[n][1] + d1);
    }
    forr(i, 0, m){
        if(used1[i] || usedn[i]){
            
            ll curr = 0;
            U = edge[i].v; V = edge[i].u; W = edge[i].c; ID = i;
            D(1); curr += d[n];
            D(n); curr += d[1];
            ans = min(ans, curr + edge[i].e);
        }
    }
    
    if(ans >= 1e18){
        cout << -1;
    }else{
        cout << ans;
    }
    
    return(0);
}

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

ho_t4.cpp: In function 'void D(long long int)':
ho_t4.cpp:49:14: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   49 |         auto [dd, u] = pq.top(); pq.pop();
      |              ^
ho_t4.cpp:51:18: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   51 |         for(auto [v, c, e, id]: adj[u]){
      |                  ^
ho_t4.cpp: In function 'void D2(long long int)':
ho_t4.cpp:73:14: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   73 |         auto [u, type, dd] = pq.top(); pq.pop();
      |              ^
ho_t4.cpp:75:18: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   75 |         for(auto [v, c, e, id]: adj[u]){
      |                  ^
ho_t4.cpp:83:22: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   83 |             for(auto [v, c, e, id]: rev[u]){
      |                      ^

• Subtask 1: 0 / 5
• Subtask 2: 0 / 11
• Subtask 3: 0 / 21
• Subtask 4: 0 / 63