Submission #419394

#	Time	Username	Problem	Language	Result	Execution time	Memory
419394		fivefourthreeone	Robot (JOI21_ho_t4)	C++17	100 / 100	898 ms	57848 KiB

Main

#pragma GCC target ("avx2")
#pragma GCC optimize ("O3")
#pragma GCC optimize ("unroll-loops")
#include <bits/stdc++.h>
#define owo(i,a, b) for(int i=(a);i<(b); ++i)
#define uwu(i,a, b) for(int i=(a)-1; i>=(b); --i)
#define senpai push_back
#define ttgl pair<int, int>
#define ayaya cout<<"ayaya~"<<endl
 
using namespace std;
using ll = long long;
using ld = long double;
const ll MOD = 1000000007;
const ll root = 3;
ll binpow(ll a,ll b){ll res=1;while(b){if(b&1)res=(res*a)%MOD;a=(a*a)%MOD;b>>=1;}return res;}
ll modInv(ll a){return binpow(a, MOD-2);}
const int INF = 0x3f3f3f3f;
const int NINF = 0xc0c0c0c0;
const ll INFLL = 0x3f3f3f3f3f3f3f3f;
const ll NINFLL = 0xc0c0c0c0c0c0c0c0;
const int mxN = 100001;
int n, m;
ll dist[mxN];
map<int, ll> trans[mxN];
map<int, ll> fdist[mxN];
vector<array<int, 3>> adj[mxN];
void solve() {
    cin>>n>>m;
    owo(i, 0, m) {
        int a, b, c, d;
        cin>>a>>b>>c>>d;
        a--; b--;
        adj[a].senpai({b, c, d});
        adj[b].senpai({a, c, d});
        trans[a][c]+=d;
        trans[b][c]+=d;
        fdist[a][c] = INFLL;
        fdist[b][c] = INFLL;
    }
    memset(dist, INFLL, sizeof(dist));
    dist[0] = 0;
    priority_queue<pair<ll, int>, vector<pair<ll, int>>, greater<pair<ll, int>>> pq;
    pq.push({0, 0});
    while(!pq.empty()) {
        auto[dx, u] = pq.top();
        //cout<<dx<<" "<<u<<" "<<dist[u]<<endl;
        pq.pop();
        if(dx!=dist[u])continue;
        for(auto v: adj[u]) {
            //transition changing all but this edge
            ll cost = min(dx, fdist[u][v[1]]) + trans[u][v[1]] - v[2];
            cost = min(cost, dx + v[2]);
            //cout<<u<<" "<<v[0]<<" "<<dx<<" "<<v[2]<<" "<<cost<<"\n";
            if(cost < dist[v[0]]) {
                dist[v[0]] = cost;
                pq.push({cost, v[0]});   
            }
            if(dx < fdist[v[0]][v[1]])fdist[v[0]][v[1]] = dx;
        }
    }
    cout<<(dist[n-1]==INFLL ? -1 : dist[n-1])<<"\n";
}
int main() {
    //freopen("file.in", "r", stdin);
    //freopen("file.out", "w", stdout);
    mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
    cin.tie(0)->sync_with_stdio(0);
    int T = 1;
    for(int tc = 1; tc <= T; tc++) {
        solve();
    }
    return 0;
}

Compilation message (stderr)

Main.cpp: In function 'void solve()':
Main.cpp:41:18: warning: overflow in conversion from 'll' {aka 'long long int'} to 'int' changes value from '4557430888798830399' to '1061109567' [-Woverflow]
   41 |     memset(dist, INFLL, sizeof(dist));
      |                  ^~~~~

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