제출 #246221

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
246221		egekabas	Olympic Bus (JOI20_ho_t4)	C++14	32 / 100	43 ms	8568 KiB

ho_t4

#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;
};
struct simple{
    ll x, y, id;
};
ll n, m;
edge e[50009];
vector<simple> inc[209];
vector<simple> out[209];
void dijkstra(ll beg, ll dis[], ll used[], ll dont[], vector<simple> g[], ll end, pll prt[]){
    for(ll i = 1; i <= n; ++i)
        dis[i] = inf;
    for(ll i = 0; i < m; ++i)
        used[i] = 0;
    dis[beg] = 0;
    priority_queue<pair<pll, pll>, vector<pair<pll, pll>>, greater<pair<pll, pll>>> pq;
    pq.push({{0, beg}, {-1, -1}});
    while(!pq.empty()){
        ll d = pq.top().ff.ff;
        ll v = pq.top().ff.ss;
        ll comeid = pq.top().ss.ff;
        ll comev = pq.top().ss.ss;
        pq.pop();
        if(dis[v] < d) continue;
        if(comeid != -1)
            prt[v] = {comeid, comev};
        for(auto u : g[v]){
            if(dont[u.id]) continue;
            if(dis[u.x] > u.y + d){
                dis[u.x] = u.y + d;
                pq.push({{dis[u.x], u.x}, {u.id , v}});
            }
        }
    }
    if(dis[end] >= inf) return;
    ll cur = end;
    while(cur != beg){
        used[prt[cur].ff] = 1;
        cur = prt[cur].ss;
    }
}
ll frombeg[2][209];
ll usedbeg[2][50009];

ll toend[2][209];
ll usedend[2][50009];

ll emptyar[50009];
ll ans[50009];
pll prt[209];
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 = 0; i < m; ++i){
        cin >> e[i].x >> e[i].y >> e[i].z >> e[i].d;
        e[i].id = i;
        inc[e[i].y].pb({e[i].x, e[i].z, e[i].id});
        out[e[i].x].pb({e[i].y, e[i].z, e[i].id});
        ans[i] += e[i].d;
    }
    ll beg = 1;
    ll end = n;
    ll fin = 0;
    dijkstra(beg, frombeg[0], usedbeg[0], emptyar, out, end, prt);
    dijkstra(beg, frombeg[1], usedbeg[1], usedbeg[0], out, end, prt);
    dijkstra(end, toend[0], usedend[0], emptyar, inc, beg, prt);
    dijkstra(end, toend[1], usedend[1], usedend[0], inc, beg, prt);
    fin += frombeg[0][end];
    for(ll i = 0; i < m; ++i){
        ll d = inf;
        if(usedbeg[0][i] == 0){
            d = min(frombeg[0][end], frombeg[0][e[i].y] + e[i].z + toend[0][e[i].x]);
            ans[i] += d;
            continue;
        }

        d = min(frombeg[1][end], frombeg[0][e[i].x]+toend[1][e[i].x]);
        d = min(d, frombeg[1][e[i].y]+toend[0][e[i].y]);
        ans[i] += d;
    }
    beg = n;
    end = 1;
    dijkstra(beg, frombeg[0], usedbeg[0], emptyar, out, end, prt);
    dijkstra(beg, frombeg[1], usedbeg[1], usedbeg[0], out, end, prt);
    dijkstra(end, toend[0], usedend[0], emptyar, inc, beg, prt);
    dijkstra(end, toend[1], usedend[1], usedend[0], inc, beg, prt);
    fin += frombeg[0][end];
    for(ll i = 0; i < m; ++i){
        ll d = inf;
        if(usedbeg[0][i] == 0){
            d = min(frombeg[0][end], frombeg[0][e[i].y] + e[i].z + toend[0][e[i].x]);
            ans[i] += d;
            continue;
        }
        d = min(frombeg[1][end], frombeg[0][e[i].x]+toend[1][e[i].x]);
        d = min(d, frombeg[1][e[i].y]+toend[0][e[i].y]);
        ans[i] += d;
    }
    for(ll i = 0; i < m; ++i){
        fin = min(fin, ans[i]);
    }
    if(fin >= inf)
        cout << -1;
    else
        cout << fin;


}

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