Submission #245473

#	Time	Username	Problem	Language	Result	Execution time	Memory
245473		egekabas	Olympic Bus (JOI20_ho_t4)	C++14	0 / 100	1090 ms	11256 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;
};
edge e[50009];
ll n, m;
ll dis[209][209];
vector<edge> g[209];
void calcdepth(ll beg, ll depth[]){
    queue<ll> q;
    q.push(beg);
    for(ll i = 1; i <= n; ++i)
        depth[i] = inf;
    depth[beg] = 0;
    while(q.size()){
        ll v = q.front();
        q.pop();
        for(edge u : g[v])
            if(dis[u.x][beg] == dis[v][beg] + u.z && depth[u.x] == inf){
                depth[u.x] = depth[v]+1;
                q.push(u.x);
            }
    }
        
}
ll d1[209];
ll dn[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;
    assert(n <= 200);
    assert(m <= 50000);
    for(ll i = 1; i <= n; ++i)
        for(ll j = 1; j <= n; ++j)
            if(i != j) dis[i][j] = inf;
    for(ll i = 0; i < m; ++i){
        cin >> e[i].x >> e[i].y >> e[i].z >> e[i].d;
        e[i].id = i;
        dis[e[i].x][e[i].y] = min(dis[e[i].x][e[i].y], e[i].z);
        g[e[i].y].pb(e[i]);
    }
    for(ll k = 1; k <= n; ++k)
        for(ll i = 1; i <= n; ++i)
            for(ll j = 1; j <= n; ++j)
                dis[i][j] = min(dis[i][j], dis[i][k]+dis[k][j]);
    calcdepth(1, d1);
    calcdepth(n, dn);
    ll ans = dis[1][n]+dis[n][1];
    for(ll i = 0; i < m; ++i){
        edge u = e[i];
        ll cur = e[i].d;
        if(dn[u.y]+1 == dn[u.x]){
            cur += min(dis[n][1], dis[n][u.x]+u.z+dis[u.y][1]);
            ll di = inf;
            for(ll j = 1; j <= n; ++j)
                if(dn[j] == dn[u.y])
                    for(auto u : g[j])
                        if(u.id != i)
                            di = min(di, dis[1][u.x]+u.z+dis[u.z][n]);
            if(dn[1] <= dn[u.y])
                di = dis[1][n];
            cur += di;
        }
        else if(d1[u.y]+1 == d1[u.x]){
            cur += min(dis[1][n], dis[1][u.x]+u.z+dis[u.y][n]);
            ll di = inf;
            for(ll j = 1; j <= n; ++j)
                if(d1[j] == d1[u.y])
                    for(auto u : g[j])
                        if(u.id != i)
                            di = min(di, dis[n][u.x]+u.z+dis[u.z][1]);
            if(d1[n] <= d1[u.y])
                di = dis[n][1];
            cur += di;
        }
        else{
            cur += min(dis[1][n], dis[1][u.y]+u.z+dis[u.x][n]);
            cur += min(dis[n][1], dis[n][u.y]+u.z+dis[u.x][1]);
        }
        ans = min(ans, cur);
    }
    if(ans >= inf)
        cout << -1;
    else
        cout << ans;
}

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