Submission #1155182

#	Time	Username	Problem	Language	Result	Execution time	Memory
1155182		hahahoang132	Olympic Bus (JOI20_ho_t4)	C++20	5 / 100	1095 ms	31776 KiB

ho_t4

#include<bits/stdc++.h>
using namespace std;
using ll = long long;
using ld = long double;
const ll N = 1e6 + 5;
const ll base = 37;
const ll inf = LLONG_MAX/4;
const ll mod = 998244353;
#define bit(x,y) ((x >> y) & 1)
ll n,m;
typedef struct
{
    ll c,d,id;
}haha;
vector<haha> a[205][205];
vector<ll> g[N];
ll d[205][205];
ll cmp(haha t1, haha t2)
{
    return t1.c + t1.d < t2.c + t2.d;
}
vector<ll> siu;
ll u[50005],v[50005],c[50005],bl,c2[50005];
ll seen[50005][2];
ll ti = 0;
ll dij()
{
    ti++;
    priority_queue<pair<ll,pair<ll,ll>>,vector<pair<ll,pair<ll,ll>>>,greater<pair<ll,pair<ll,ll>>>> pq;
    pq.push({0,{1,0}});
    while(!pq.empty())
    {
        ll dis = pq.top().first;
        ll x = pq.top().second.first;
        ll t = pq.top().second.second;
        pq.pop();
        if(seen[x][t] == ti) continue;
        seen[x][t] = ti;
        if(x == 1 && t == 1) return dis;
        for(auto id : g[x])
        {
            if(id == bl) continue;
            ll y = v[id];
            ll add = c[id];
            ll nt = t;
            if(y == n) nt = 1;
            if(seen[y][nt] != ti) pq.push({dis + add,{y,nt}});
        }
    }
    return inf;
}
int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    cin >> n >> m;
    ll i,j;
    for(i = 1;i <= n;i++)
    {
        for(j = 1;j <= n;j++)
        {
            d[i][j] = inf;
        }
        d[i][i] = 0;
    }
    for(i = 1;i <= m;i++)
    {
        cin >> u[i] >> v[i] >> c[i] >> c2[i];
        d[u[i]][v[i]] = min(d[u[i]][v[i]],c[i]);
        g[u[i]].push_back(i);
        haha tmp;
        tmp.c = c[i];
        tmp.d = c2[i];
        tmp.id = i;
        a[u[i]][v[i]].push_back(tmp);
    }
    for(i = 1;i <= n;i++)
    {
        for(j = 1;j <= n;j++)
        {
            if(i == j) continue;
            sort(a[i][j].begin(),a[i][j].end(),cmp);
            if(a[i][j].size() >= 1)
            {
                if(a[i][j][0].c + a[i][j][0].d < d[j][i])
                {
                    siu.push_back(a[i][j][0].id);
                }
            }
            if(a[i][j].size() >= 2)
            {
                if(a[i][j][1].c + a[i][j][1].d < d[j][i])
                {
                    siu.push_back(a[i][j][1].id);
                }
            }
        }
    }
    //cout << siu.size();
    ll ans = dij();
    for(auto sus : siu)
    {
        v[m + 1] = u[sus];
        u[m + 1] = v[sus];
        c[m + 1] = c[sus];
        bl = sus;
        g[v[sus]].push_back(m + 1);
        ans = min(ans,dij() + c2[sus]);
        g[v[sus]].pop_back();
    }
    if(ans == inf) cout << -1;
    else cout << ans;
}

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