| # | Time | Username | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 635553 | Trent | Robot (JOI21_ho_t4) | C++14 | 0 ms | 0 KiB |
This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#include "bits/stdc++.h"
#include <unordered_map>
using namespace std;
#define ll long long
#define open(g) string _name_ = g; freopen((_name_ + ".in").c_str(), "r", stdin); freopen((_name_ + ".out").c_str(), "w", stdout)
#define printArr(a, len) for(int asdf = 0; asdf < (len); ++asdf) cout << (a)[asdf] << ' '; cout << '\n';
#define boost() cin.sync_with_stdio(0); cin.tie(0)
#define forR(i, x) for(int i = 0; i < x; ++i)
#define REP(i, a, b) for(int i = (a); i < (b); ++i)
#define all(i) i.begin(), i.end()
#define pii pair<int, int>
#define vi vector<int>
#define si set<int>
#define usi unordered_set<int>
#define mii map<int, int>
#define umii unordered_map<int, int>
const int MN = 3e5 + 10;
const ll INF = 1e16;
struct edge{int n, c1, c2, p;};
struct node{int i, cc; ll d;}; // node, color channel (0 for none), distance
bool operator <(const node& a, const node& b){ return a.d > b.d; }
vector<edge> adj[MN];
vector<vector<edge>> ce[MN];
vector<ll> cs[MN], dis[MN];
// gp_hash_table<int, vector<edge>> ce[MN]; // colors split into channels
// gp_hash_table<int, ll> cs[MN]; // color sum of each node
// gp_hash_table<int, ll> dis[MN];
gp_hash_table<int, int> ci[MN];
signed main(){
boost();
int N, M; cin >> N >> M;
REP(i, 1, N + 1) cs[i].push_back(0), dis[i].push_back(INF), ce[i].emplace_back();
forR(i, M){
int a, b, c, p; cin >> a >> b >> c >> p;
if(ci[a].find(c) == ci[a].end()) ci[a][c] = ce[a].size(), cs[a].push_back(0), dis[a].push_back(INF), ce[a].emplace_back();
if(ci[b].find(c) == ci[b].end()) ci[b][c] = ce[b].size(), cs[b].push_back(0), dis[b].push_back(INF), ce[b].emplace_back();
adj[a].push_back({b, ci[a][c], ci[b][c], p}); adj[b].push_back({a, ci[b][c], ci[a][c], p});
}
REP(i, 1, N + 1){
dis[i][0] = INF;
for(auto [n, c1, c2, p] : adj[i]) cs[i][c1] += p, dis[i][c1] = INF, ce[i][c1].push_back({n, c1, c2, p});
}
priority_queue<node> dij;
dij.push({1, 0, 0});
dis[1][0] = 0;
while(!dij.empty()){
auto [i, cc, d] = dij.top(); dij.pop();
if(cc == 0){
for(auto [n, c1, c2, p] : adj[i]) {
ll oc = cs[i][c1] - p;
if(dis[i][0] + min(oc, (ll) p) < dis[n][0]){
dis[n][0] = dis[i][0] + min(oc, (ll) p);
dij.push({n, 0, dis[n][0]});
}
if(c1 != 0 && dis[i][0] < dis[n][c2]){
dis[n][c2] = dis[i][0];
dij.push({n, c2, dis[n][c2]});
}
}
} else {
for(auto [n, c1, c2, p] : ce[i][cc]){
ll cos = cs[i][cc] - p;
if(dis[i][cc] + cos < dis[n][0]){
dis[n][0] = dis[i][cc] + cos;
dij.push({n, 0, dis[n][0]});
}
}
}
}
cout << (dis[N][0] >= INF ? -1 : dis[N][0]) << '\n';
}