Submission #1181510

#	Time	Username	Problem	Language	Result	Execution time	Memory
1181510		mikras	Robot (JOI21_ho_t4)	C++20	34 / 100	3097 ms	72484 KiB

Main

//Mikolaj Tofiluk
#include <bits/stdc++.h>
using namespace std;
using ll=long long;
constexpr int MAXN=100007;
ll INF=1e18;
map<int,ll> odl[MAXN];//0 - bez zmiany, 1 - przyszedl z zmienionej oryginalnie 1, 2 - przyszedl z zmienionej oryginalnie 2
vector<pair<int,pair<int,ll>>> graf[MAXN];//kolor u cena-zmiany
map<int,ll> suma_cen[MAXN];
map<int,bool> odw[MAXN];
int n,m;
void fastscan_ll(ll &number) {
    bool negative = false;
    register char c;
    number = 0;
    c = getchar();
    if (c=='-'){
        negative = true;
        c = getchar();
    }
    for (; (c>47 && c<58); c=getchar())
        number = number *10 + c - 48;
    if (negative)
        number *= -1;
}

void fastscan_int(int &number) {
    bool negative = false;
    register char c;
    number = 0;
    c = getchar();
    if (c=='-'){
        negative = true;
        c = getchar();
    }
    for (; (c>47 && c<58); c=getchar())
        number = number *10 + c - 48;
    if (negative)
        number *= -1;
}

void wczytanie(){
    fastscan_int(n);fastscan_int(m);
    int a,b,k;
    ll c;
    for (int i=0;i<m;i++){
        fastscan_int(a);fastscan_int(b);fastscan_int(k);fastscan_ll(c);
        graf[a].push_back({k,{b,c}});
        graf[b].push_back({k,{a,c}});
        suma_cen[a][k]+=c;
        suma_cen[b][k]+=c;
    }
}
void djikstra(){
    for (int i=1;i<=n;i++){
        odl[i][0]=INF;
        for (pair<int,pair<int,ll>> u:graf[i]) odl[i][u.first]=INF;
    }
    priority_queue<pair<pair<ll,int>,int>> q; //cena v kolor_tej_co_zmienilem
    q.push({{0,1},0});
    odl[1][0]=0;
    int v,kolor,u,x;
    ll c,xc;
    while (q.size()>0){
        v=q.top().first.second;
        x=q.top().second;
        q.pop();
        if (odw[v][x]) continue;
        odw[v][x]=1;
        for (pair<int,pair<int,ll>> syf:graf[v]){
            kolor=syf.first;u=syf.second.first;c=syf.second.second;
            if (x==0 && odl[v][x]+min(suma_cen[v][kolor]-c,c)<odl[u][0]){
                odl[u][0]=min(suma_cen[v][kolor]-c,c)+odl[v][x];
                q.push({{-odl[u][0],u},0});
            }
            if (x==0 && odl[u][kolor]>odl[v][x]){
                odl[u][kolor]=odl[v][x];
                q.push({{-odl[u][kolor],u},kolor});
            }
            if (x!=0 && kolor==x && odl[u][0]>odl[v][x]+suma_cen[v][x]-c){
                odl[u][0]=odl[v][x]+suma_cen[v][x]-c;
                q.push({{-odl[u][0],u},0});
            }
        }
    }
}
int main(){
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    wczytanie();
    djikstra();
    ll w=odl[n][0];
    if (w==INF) cout<<-1;
    else cout<<w;
}

Compilation message (stderr)

Main.cpp: In function 'void fastscan_ll(ll&)':
Main.cpp:14:19: warning: ISO C++17 does not allow 'register' storage class specifier [-Wregister]
   14 |     register char c;
      |                   ^
Main.cpp: In function 'void fastscan_int(int&)':
Main.cpp:29:19: warning: ISO C++17 does not allow 'register' storage class specifier [-Wregister]
   29 |     register char c;
      |                   ^

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