제출 #1156747

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1156747		dosts	Robot (JOI21_ho_t4)	C++17	24 / 100	924 ms	124648 KiB

Main

#include <bits/stdc++.h>
#pragma GCC optimize("O3,unroll-loops")
#pragma GCC target("avx2")
using namespace std;
#define int long long
#define pii pair<int,int>
#define ff first
#define ss second
#define sp << " " <<    
#define all(cont) cont.begin(),cont.end()
#define vi vector<int>

const int inf = 1e18,N = 5e5+1,MOD =  998244353;


struct Edge {
    int to,price,id;
};

void solve() {  
    int n,m;
    cin >> n >> m;
    unordered_map<int,vector<Edge>> edges[n+1];
    unordered_map<int,int> sms[n+1];
    vector<Edge> alledges[n+1];
    vector<Edge> edg(m+1);
    for (int i=1;i<=m;i++) {
        int a,b,c,p;
        cin >> a >> b >> c >> p;
        edg[i] = {b,p,c};
        edges[a][c].push_back({b,p,i});
        edges[b][c].push_back({a,p,i});
        alledges[a].push_back({b,p,i});
        alledges[b].push_back({a,p,i});
        sms[a][c]+=p;
        sms[b][c]+=p;
    }
    vi dp(n+1,inf);
    unordered_map<int,int> dpp[n+1];
    for (int i=1;i<=n;i++) {
        for (auto it : sms[i]) {
            dpp[i][it.ff] = inf;
        }
    }
    dp[1] = 0;
    using State = pair<int,pair<int,pii>>;
    priority_queue<State,vector<State>,greater<State>> pq;
    pq.push({0,{0,{1,0}}});
    while (!pq.empty()) {
        auto[c,pr] = pq.top();
        auto[typ,ppr] = pr;
        auto[node,id] = ppr;
        pq.pop();
        if (typ == 0) {
            if (dp[node] < c) continue;
            for (Edge e : alledges[node]) {
                if (dp[e.to] > c+sms[node][edg[e.id].id]-e.price) {
                    dp[e.to] = c+sms[node][edg[e.id].id]-e.price;
                    pq.push({dp[e.to],{0,{e.to,0}}});
                }
                if (dp[e.to] > c+e.price) {
                    dp[e.to] = c+e.price;
                    pq.push({dp[e.to],{0,{e.to,0}}});
                }
                if (dpp[e.to][edg[e.id].id] > c+e.price) {
                    dpp[e.to][edg[e.id].id] = c+e.price;
                    pq.push({dpp[e.to][edg[e.id].id],{1,{e.to,e.id}}});
                }
            }
        }
        else {
            int col = edg[id].id;
            int pri = edg[id].price;
            if (dpp[node][col] < c) continue;
            for (Edge e : edges[node][col]) {
                if (e.id == id) continue;
                if (dp[e.to] > c+sms[node][edg[e.id].id]-pri-e.price) {
                    dp[e.to] = c+sms[node][edg[e.id].id]-pri-e.price;
                    pq.push({dp[e.to],{0,{e.to,0}}});
                }
                if (dp[e.to] > c+e.price) {
                    dp[e.to] = c+e.price;
                    pq.push({dp[e.to],{0,{e.to,0}}});
                }
                if (dpp[e.to][edg[e.id].id] > c+e.price) {
                    dpp[e.to][edg[e.id].id] = c+e.price;
                    pq.push({dpp[e.to][edg[e.id].id],{1,{e.to,e.id}}});
                }
            }
        }
    }
    int ans = dp[n];
    for (auto it : dpp[n]) ans = min(ans,it.ss);
    if (ans >= inf) cout << -1 << '\n';
    else cout << ans << '\n';
}


int32_t main() { 
    ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
    #ifdef Dodi 
        freopen("in.txt","r",stdin);
        freopen("out.txt","w",stdout);
    #endif
    int t = 1;
    //cin >> t;
    while (t --> 0) solve();
}

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