Submission #1028460

#	Time	Username	Problem	Language	Result	Execution time	Memory
1028460		snpmrnhlol	Robot (JOI21_ho_t4)	C++17	100 / 100	454 ms	79676 KiB

Main

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll N = 1e5;
const ll M = 2e5;
const ll inf = 1e18;
vector<pair<ll,ll>>e[N+M*2];
ll dist[N+M*2];
map <ll,ll> f[N];
vector <array<ll,3>> edges[M];
priority_queue <pair<ll,ll>> pq;
ll vis[N];
ll cnt = 0;
int main(){
    ll n,m;
    cin>>n>>m;
    for(ll i = 0;i < m;i++){
        ll u,w,c,d;
        cin>>u>>w>>c>>d;
        u--;w--;c--;
        f[u][c]+=d;
        f[w][c]+=d;
        edges[c].push_back({u,w,d});
    }
    ///two consective of the same color has a special case
    ///how to implement??? is the only way to make additions to graph?? ew
    cnt = n;
    for(ll i = 0;i < m;i++){
        for(auto j:edges[i]){
            e[j[0]].push_back({j[1],min(j[2],f[j[0]][i] - j[2])});
            e[j[1]].push_back({j[0],min(j[2],f[j[1]][i] - j[2])});
            if(!vis[j[0]]){
                vis[j[0]] = cnt++;
            }
            if(!vis[j[1]]){
                vis[j[1]] = cnt++;
            }
            //cout<<vis[j[0]]<<' '<<vis[j[1]]<<'\n';
            e[j[1]].push_back({vis[j[0]],0});
            e[j[0]].push_back({vis[j[1]],0});
            e[vis[j[0]]].push_back({j[1],f[j[0]][i] - j[2]});
            e[vis[j[1]]].push_back({j[0],f[j[1]][i] - j[2]});
        }
        for(auto j:edges[i]){
            vis[j[0]] = 0;
            vis[j[1]] = 0;
        }
    }
    for(ll i = 0;i < cnt;i++){
        dist[i] = inf;
    }
    dist[0] = 0;
    pq.push({0,0});
    while(!pq.empty()){
        ll d = -pq.top().first;
        ll id = pq.top().second;
        pq.pop();
        if(d > dist[id])continue;
        for(auto i:e[id]){
            if(dist[i.first] > i.second + d){
                dist[i.first] = i.second + d;
                pq.push({-dist[i.first],i.first});
            }
        }
    }
    if(dist[n - 1] == inf)dist[n - 1] = -1;
    cout<<dist[n - 1]<<'\n';
    return 0;
}

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