Submission #811884

#	Time	Username	Problem	Language	Result	Execution time	Memory
811884		vjudge1	Olympic Bus (JOI20_ho_t4)	C++14	5 / 100	109 ms	2844 KiB

ho_t4

#include<bits/stdc++.h>
#define fi first
#define se second
#define ll long long
using namespace std ;
const ll N = 200, M = 5e4 ;
ll n, m, from[M + 1], to[M + 1], c[M + 1], d[M + 1] ;
set<pair<ll, ll>> v[N + 1] ;
ll deikstra(ll city, ll abu)
{
    ll dist[N + 1] ;
    set<pair<ll, ll>> s ;
    for(ll i = 1 ; i <= N ; i++)
        dist[i] = 1e15 ;
    dist[city] = 0 ;
    s.insert({0, city}) ;
    while(s.size())
    {
        pair<ll, ll> p = *s.begin() ;
        s.erase(p) ;
//        cout << p.fi << ' ' << p.se << '\n' ;
        if(p.fi > dist[p.se])
            continue ;
        for(auto i : v[p.se])
        {
            if(dist[i.fi] > p.fi + i.se)
            {
//                cout<<p.se<<"->"<<i.fi<<'\n';
                dist[i.fi] = p.fi + i.se ;
                s.insert({dist[i.fi], i.fi}) ;
            }
        }
    }
    return dist[abu] ;
}
signed main()
{
    ios_base::sync_with_stdio( 0 ) ;
    cin.tie( 0 ) ;
    cout.tie( 0 ) ;
    cin >> n >> m ;
    for(ll i = 1 ; i <= m ; i++)
        cin >> from[i] >> to[i] >> c[i] >> d[i] ;
    if(m <= 1000)
    {
        ll ans ;
        for(ll i = 1 ; i <= m ; i++)
            v[from[i]].insert({to[i], c[i]}) ;
        ans = deikstra(1, n) + deikstra(n, 1) ;
        for(ll i = 1 ; i <= m ; i++)
        {
            ll now = d[i] ;
            v[from[i]].erase({to[i], c[i]}) ;
            v[to[i]].insert({from[i], c[i]}) ;
            now += deikstra(1, n) ;
            now += deikstra(n, 1) ;
            ans = min(ans, now) ;
//            cout << "___________________\n" ;
            v[to[i]].erase({from[i], c[i]}) ;
            v[from[i]].insert({to[i], c[i]}) ;
        }
        if(ans >= 1e15)
            ans = -1 ;
        cout << ans ;
        return 0 ;
    }
    return 0 ;
}

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