Submission #1147875

#	Time	Username	Problem	Language	Result	Execution time	Memory
1147875		ByeWorld	Robot (JOI21_ho_t4)	C++20	100 / 100	1069 ms	170920 KiB

Main

#include <bits/stdc++.h>
#define int long long
#define ll long long
#define pb push_back
#define fi first
#define se second
#define lf (id<<1)
#define rg ((id<<1)|1)
#define md ((l+r)>>1)
#define ld long double
using namespace std;
typedef pair<int,int> pii;
typedef pair<char,char> pcc;
typedef pair<pii,int> ipii;
typedef pair<pii,pii> ipiii;
const int MAXN = 3e5+10;
const int SQRT = 300;
const int MAXA = 50;
const int LOG = 20;
const int INF = 1e18+10;
const ld EPS = 1e-12;
const int MOD = 1e9+7;
void chsum(int &a, int b){ a = (a+b)%MOD; }
void chmn(int &a, int b){ a = min(a, b); }
void chmx(int &a, int b){ a = max(a, b); }

int n, m;
map<int,int> sum[MAXN], dp1[MAXN];
map<int,vector<pii>> adjc[MAXN];
vector <ipii> adj[MAXN];

int dp[MAXN];
priority_queue <ipii, vector<ipii>, greater<ipii>> pq;
void DJI(){
    for(int i=1; i<=n; i++) dp[i] = INF;
    pq.push({{0,0}, 1});
    while(!pq.empty()){
        int dis = pq.top().fi.fi, tag = pq.top().fi.se, nw = pq.top().se;
        pq.pop();
        // cout << "p\n";

        if(tag==0){
            if(dp[nw] != INF) continue;
            dp[nw] = dis;
            // cout << nw << ' '<< dis << " dis\n";

            for(auto [a, wei] : adj[nw]){
                int nx = a.fi, col = a.se;
                // ganti ed
                pq.push({{dis+wei, 0}, nx});
                // ganti semua kecual ed
                pq.push({{dis+sum[nw][col]-wei, 0}, nx});
                // ganti col tp di nx
                pq.push({{dis, col}, nx});
            }
        } else {
            if(dp1[nw].count(tag)) continue;
            dp1[nw][tag] = dis;

            for(auto [nx, wei] : adjc[nw][tag]){
                pq.push({{dis+sum[nw][tag]-wei, 0}, nx});
            }
        }
    }
}
signed main(){
    // ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
    cin>>n>>m;
    for(int i=1; i<=m; i++){
        int x,y,c,wei;cin>>x>>y>>c>>wei;
        adj[x].pb({{y,c}, wei});
        adj[y].pb({{x,c}, wei});

        adjc[x][c].pb({y, wei});
        adjc[y][c].pb({x, wei});

        sum[x][c] += wei;
        sum[y][c] += wei;
    }
    DJI();
    cout << (dp[n]==INF ? -1 : dp[n]) << '\n';
}

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