제출 #1258955

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1258955		notisora	Robot (JOI21_ho_t4)	C++20	100 / 100	468 ms	57172 KiB

Main

///NotIsora
///This is my last dance
#include<bits/stdc++.h>
#define modulo 1000000007
#define fi first
#define se second
#define sq(x) (x)*(x)
#define ll long long
#define ld long double
#define el '\n'
#define pb push_back
///#define int long long

using namespace std;

const int N=1e5+5;
const ll INF=1e15;

struct Edge{
    int nx,c,p;
    bool operator < (const Edge&other) const{
        return c<other.c;
    }
};
vector<Edge>adj[N];
map<int,ll>sum[N];
int n,m;
map<int,ll>d[N];

struct State{
    int s,c;
    ll dis;
    bool operator < (const State&other) const{
        return dis>other.dis;
    }
};

void dijkstra(){
    priority_queue<State>pq;
    pq.push({1,0,0});
    d[1][0]=0;

    while(!pq.empty()){
        ll dis=pq.top().dis;
        int s=pq.top().s;
        int color=pq.top().c;
        pq.pop();

        if (d[s][color]<dis) continue;

        if (color==0){
            for(int i=0;i<(int)adj[s].size();i++){
                int u=adj[s][i].nx;
                int w=adj[s][i].p;
                int c=adj[s][i].c;

                if (!d[u].count(c)) d[u][c]=INF;
                if (!d[u].count(0)) d[u][0]=INF;

                if (d[u][c]>dis){
                    d[u][c]=dis;
                    pq.push({u,c,dis});
                }
                ///Reset mau = doi het mau canh khac hoac doi mau canh hien tai
                if (d[u][0]>dis+min(sum[s][c]-(ll)w,(ll)w)){
                    d[u][0]=dis+min(sum[s][c]-(ll)w,(ll)w);
                    pq.push({u,0,d[u][0]});
                }
            }
        }

        else{
            auto it=lower_bound(adj[s].begin(),adj[s].end(),Edge({0,color,0}));
            for(;it!=adj[s].end();it++){
                int u=it->nx;
                int w=it->p;
                int c=it->c;

                if (c!=color) break;
                if (!d[u].count(0)) d[u][0]=INF;

                if (d[u][0]>dis+sum[s][c]-(ll)w){
                    d[u][0]=dis+sum[s][c]-(ll)w;
                    pq.push({u,0,d[u][0]});
                }
            }
        }

    }
}

signed main(){
    ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
    //freopen("i.INP","r",stdin);
    cin>>n>>m;

    for(int i=1;i<=m;i++){
        int a,b,c,p;
        cin>>a>>b>>c>>p;
        adj[a].pb({b,c,p});
        adj[b].pb({a,c,p});
        sum[a][c]+=(ll)p;
        sum[b][c]+=(ll)p;
    }

    for(int i=1;i<=n;i++){
        sort(adj[i].begin(),adj[i].end());
    }

    dijkstra();

    if (!d[n].count(0) || d[n][0]==INF) cout<<-1;
    else cout<<d[n][0];
}

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