Submission #1055605

#	Time	Username	Problem	Language	Result	Execution time	Memory
1055605		HuyAT	Robot (JOI21_ho_t4)	C++14	100 / 100	1704 ms	95860 KiB

Main

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

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,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;
    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,0});
    f[{1,-1}] = 0;
    while(!pq.empty()){
        Data t = pq.top();
        DP d = {t.v,t.c};
        pq.pop();
        if(t.w > f[d]){
            continue;
        }

//        if(t.v == 10){
//            std::cerr << t.w << newl;
//            std::cerr << "STOP\n";
//        }
//        if(t.v == 8){
//            std::cerr << "STOP";
//        }
//        assert((f.find({n,-1}) == f.end() || f[{n,-1}] != 0));
        if(t.c == -1){
            for(const auto &l : adj[t.v]){
                for(const auto &nxt : l.second){
                    DP nD = {nxt.first,-1};
                    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,nW});
                    }
                    nD = {nxt.first,-2};
                    nW = t.w + nxt.second;
                    if(f.find(nD) == f.end() || nW < f[nD]){
                        f[nD] = nW;
                        pq.push({nD.v,nD.c,nW});
                    }
                    nD = {nxt.first,-3};
                    nW = t.w + nxt.second;
                    if(f.find(nD) == f.end() || nW < f[nD]){
                        f[nD] = nW;
                        pq.push({nD.v,nD.c,nW});
                    }
                    nD = {nxt.first,l.first};
                    nW = t.w;
                    if(f.find(nD) == f.end() || nW < f[nD]){
                        f[nD] = nW;
                        pq.push({nD.v,nD.c,nW});
                    }
                }
            }
        }else if(t.c == -2){
            for(const auto &l : adj[t.v]){
                for(const auto &nxt : l.second){
                    DP nD = {nxt.first,l.first};
                    long long nW = t.w;
                    if(f.find(nD) == f.end() || nW < f[nD]){
                        f[nD] = nW;
                        pq.push({nD.v,nD.c,nW});
                    }
                    nD = {nxt.first,-2};
                    nW = t.w + nxt.second;
                    if(f.find(nD) == f.end() || nW < f[nD]){
                        f[nD] = nW;
                        pq.push({nD.v,nD.c,nW});
                    }
                    nD = {nxt.first,-3};
                    nW = t.w + nxt.second;
                    if(f.find(nD) == f.end() || nW < f[nD]){
                        f[nD] = nW;
                        pq.push({nD.v,nD.c,nW});
                    }
                }
            }
        }else if(t.c == -3){
            for(const auto &l : adj[t.v]){
                for(const auto &nxt : l.second){
                    if(l.first == t.c){
                        continue;
                    }
                    DP nD = {nxt.first,-1};
                    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,nW});
                    }
                }
            }
        }else{
            for(const auto &nxt : adj[t.v][t.c]){
                DP nD = {nxt.first,-1};
                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,nW});
                }
            }
        }

    }
    long long ans = INF;
    DP d = {n,-1};
    DP d1 = {n,-2};
    if(f.find(d) != f.end()){
        ans = std::min(ans,f[d]);
    }
    if(f.find(d1) != f.end()){
        ans = std::min(ans,f[d1]);
    }
    return (ans == INF ? -1 : ans);
}
int 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: 42 / 42