Submission #450520

#	Time	Username	Problem	Language	Result	Execution time	Memory
450520		SirCovidThe19th	Robot (JOI21_ho_t4)	C++17	100 / 100	1498 ms	86792 KiB

Main

#include <bits/stdc++.h>
using namespace std; 

#define ll long long

const int mx = 1e5+5;

int n, m; map<int, vector<tuple<int, int>>> adj[mx]; 
map<int, ll> tot[mx], dst[mx];
priority_queue<tuple<ll, int, int>> pq;

void add(int b, int c, ll val){
    if (val < dst[b][c]) dst[b][c] = val, pq.push({-val, b, c});
}

int main(){
    cin >> n >> m;
    for (int i = 0; i < m; i++){
        int a, b, c, w; cin >> a >> b >> c >> w;
        adj[a][c].push_back({b, w});
        adj[b][c].push_back({a, w});
        tot[a][c] += w; tot[b][c] += w;
        dst[a][c] = dst[b][c] = 1e18;
    }for (int i = 1; i <= n; i++) dst[i][0] = 1e18;
	dst[1][0] = 0; pq.push({0, 1, 0});
    while (!pq.empty()){
        ll cst; int A, C; tie(cst, A, C) = pq.top(); cst *= -1; pq.pop();
        if (cst != dst[A][C]) continue;
        if (C){
            for (auto [b, w] : adj[A][C])
                add(b, 0, tot[A][C] - w + cst);
        }else{
            for (auto c : adj[A]) for (auto [b, w] : c.second){ 
                add(b, 0, tot[A][c.first] - w + cst);
                add(b, 0, w + cst);
                add(b, c.first, cst);
            }
        }
    }cout<<(dst[n][0] == 1e18 ? -1 : dst[n][0])<<endl;
}
 

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