Submission #846997

#	Time	Username	Problem	Language	Result	Execution time	Memory
846997		smirichto	Robot (JOI21_ho_t4)	C++17	0 / 100	150 ms	27496 KiB

Main

#include<bits/stdc++.h>

using namespace std;
typedef long long ll;
typedef long double ld;
#define pb push_back
#define pi pair<ll,ll>
#define F first
#define S second
#define all(x) (x).begin(), (x).end()
#define alll(x) ((x).begin()+1), (x).end()
#define clean(v) (v).resize(distance((v).begin(), unique(all(v))));
#define yes cout<<"Yes"<<endl;
#define no cout<<"No"<<endl;
#define mod mod
#define endl '\n'
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
const ll mod = 998244353;

void io() {
    ios::sync_with_stdio(false);
    cin.tie(NULL);
}

template<class T>
bool ckmax(T &a, const T &b) { return a < b ? a = b, 1 : 0; }

template<class T>
bool ckmin(T &a, const T &b) { return a > b ? a = b, 1 : 0; }

void nop() {
    cout << -1 << endl;
    return;
}

const ll N = 2e5+5 ;
vector<array<ll,4>> adj[N] ;

void solve() {
    ll n , m ;
    cin>>n>>m ;
    for(ll i = 1 ; i<=m ; i++){
        ll u , v , c , p ;
        cin>>u>>v>>c>>p ;
        adj[u].pb({v , c , p}) ;
        adj[v].pb({u , c, p}) ;
    }
    priority_queue<array<ll , 2> , vector<array<ll,2>> , greater<>> pq ;
    pq.push({ 0 , 1}) ;
    vector<ll> dist(n+1 , 1e17) ;
    vector<ll> sum(m+1) ;
    dist[1] = 0 ;
    while(!pq.empty()){
        auto a = pq.top() ; pq.pop() ;
        ll node = a[1] , w = a[0] ;
        if(dist[node]!=w) continue;
        for(auto p : adj[node]){
            ll col = p[1] , cost = p[2] ;
            sum[col] += cost ;
        }
        set<pi> s ;
        for(auto p : adj[node]){
            ll col = p[1];
            s.insert({sum[col] , col}) ;
        }

        for(auto p : adj[node]){
            ll to = p[0] , col = p[1] , cost = p[2] ;
            ll d = sum[col] - cost ;
            auto it = s.begin() ;
            if(it->second != col) ckmin(d , it->first + cost) ;
            if(s.size()>1){
                ++it ;
                if(it->second != col) ckmin(d , it->first + cost) ;
            }
            if(s.size()<m) ckmin(d , (ll)cost) ;
            if(ckmin(dist[to] , d + w)){
                pq.push({dist[to] , to}) ;
            }
        }

        for(auto p : adj[node]){
            ll col = p[1] , cost = p[2] ;
            sum[col] -= cost ;
        }
    }
    ll ans = dist[n] ;
    if(ans>=1e17) ans = -1 ;
    cout<<ans<<endl;
}

int main() {
//#ifndef ONLINE_JUDGE
//    freopen("input.in", "r", stdin);
//    freopen("output.out", "w", stdout);
//#endif
    io();
    ll tt = 1;
    //cin>>tt ;
    while (tt--) {
        solve();
    }

    return 0;
}

Compilation message (stderr)

Main.cpp: In function 'void solve()':
Main.cpp:76:24: warning: comparison of integer expressions of different signedness: 'std::set<std::pair<long long int, long long int> >::size_type' {aka 'long unsigned int'} and 'll' {aka 'long long int'} [-Wsign-compare]
   76 |             if(s.size()<m) ckmin(d , (ll)cost) ;
      |                ~~~~~~~~^~

• Subtask 1: 0 / 34
• Subtask 2: 0 / 24
• Subtask 3: 0 / 42