제출 #1053980

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1053980		HuyAT	Robot (JOI21_ho_t4)	C++14	58 / 100	1012 ms	89820 KiB

Main

#include<bits/stdc++.h>
#define newl '\n'
#define int long long


const int N = 1e5 + 10;
const int V = 1e7 + 10;
const long long INF = 1e18;
const long long M = 1e9 + 7;

struct Data{
    long long v,c,par,w;
    bool operator > (const Data &other) const {
        return (w > other.w);
    }
//    bool operator < (const Data &other) const {
//        return (w < other.w);
//    }
};
struct DP{
    long long v,c,par;
    bool operator < (const DP &other) const {
        return (v < other.v || (v == other.v && c < other.c));
    }
};
std::map<int,std::vector<std::pair<int,int>>> adj[N + 1];
std::map<DP,long long> f;
std::map<std::pair<int,int>,long long> s;

int n,m;

void readData(){
    std::cin >> n >> m;
    for(int i = 1;i <= m;++i){
        int u,v,c,w;
        std::cin >> u >> v >> c >> w;
        adj[u][c].emplace_back(v,w);
        adj[v][c].emplace_back(u,w);
    }
}
void precompute(){
    for(int i = 1;i <= n;++i){
        for(const auto &t : adj[i]){
            for(const auto &p : t.second){
                s[{i,t.first}] += p.second;
            }
        }
    }
}
long long solve(){
    std::priority_queue<Data,std::vector<Data>,std::greater<Data>> pq;
    pq.push({1,-1,-1,0});
    f[{1,-1,-1}] = 0;
    while(!pq.empty()){
        Data t = pq.top();
        DP d = {t.v,t.c,t.par};
        pq.pop();
        if(t.w > f[d]){
            continue;
        }
        if(t.c == -1){
            for(const auto &l : adj[t.v]){
                for(const auto &nxt : l.second){
                    if(nxt.first == t.par){
                        continue;
                    }
                    DP nD = {nxt.first,-1,t.v};
                    long long nW = t.w + s[{t.v,l.first}] - nxt.second;
                    if(f.find(nD) == f.end() || nW < f[nD]){
                        f[nD] = nW;
                        pq.push({nD.v,nD.c,t.v,nW});
                    }
                    nD = {nxt.first,-2,t.v};
                    nW = t.w + nxt.second;
                    if(f.find(nD) == f.end() || nW < f[nD]){
                        f[nD] = nW;
                        pq.push({nD.v,nD.c,t.v,nW});
                    }
                    nD = {nxt.first,l.first,t.v};
                    nW = t.w;
                    if(f.find(nD) == f.end() || nW < f[nD]){
                        f[nD] = nW;
                        pq.push({nD.v,nD.c,t.v,nW});
                    }

                }
            }
        }else if(t.c == -2){
            for(const auto &l : adj[t.v]){
                for(const auto &nxt : l.second){
                    if(nxt.first == t.par){
                        continue;
                    }
                    DP nD = {nxt.first,l.first,t.v};
                    long long nW = t.w;
                    if(f.find(nD) == f.end() || nW < f[nD]){
                        f[nD] = nW;
                        pq.push({nD.v,nD.c,t.v,nW});
                    }
                    nD = {nxt.first,-2,t.v};
                    nW = t.w + nxt.second;
                    if(f.find(nD) == f.end() || nW < f[nD]){
                        f[nD] = nW;
                        pq.push({nD.v,nD.c,t.v,nW});
                    }
                }
            }
        }else{
            for(const auto &nxt : adj[t.v][t.c]){
                DP nD = {nxt.first,-1,t.par};
                long long nW = t.w + s[{t.v,t.c}] - nxt.second;
                if(f.find(nD) == f.end() || nW < f[nD]){
                    f[nD] = nW;
                    pq.push({nD.v,nD.c,t.v,nW});
                }
            }
        }

    }
    long long ans = INF;
    for(const auto &t : f){
        if(t.first.c < 0 && t.first.v == n){
            ans = std::min(ans,t.second);
        }
    }
    return (ans == INF ? -1 : ans);
}
signed main(){
    std::ios_base::sync_with_stdio(false);
    std::cin.tie(nullptr);std::cout.tie(nullptr);
    readData();
    precompute();
    std::cout << solve();
    return 0;
}

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