| # | Time | Username | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 390332 | oleksg | Robot (JOI21_ho_t4) | C++11 | 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.
#pragma GCC optimize("O2")
#include <fstream>
#include <string>
#include <iostream>
#include <bitset>
#include <math.h>
#include <string>
#include <algorithm>
#include <assert.h>
#include <bits/stdc++.h>
#include <vector>
#include <queue>
#include<stdio.h>
#include<ctype.h>
#define ll long long
using namespace std;
ll n, m;
struct con{
ll d;
ll color;
ll cost;
};
vector<con> cons[100001];
unordered_map<int, ll> cost[100001];
// how much to convert all nodes of a color to some other color
unordered_map<int, ll> dist[100001];
ll dist2[100001];
unordered_map<int, int> used[100001];
//if node with color x was used
int main(){
cin.tie(0)->sync_with_stdio(0);
cin >> n >> m;
int one, two, thre
ll four;
for (int x = 0; x < m; x++){
cin >> one >> two >> three >> four;
cons[one - 1].push_back({two - 1, three, four});
cons[two - 1].push_back({one - 1, three, four});
}
for (int x = 0; x < n; x++){
for (int y = 0; y < cons[x].size(); y++){
int col = cons[x][y].color;
ll cst = cons[x][y].cost;
if (cost[x].find(col) == cost[x].end()){
cost[x][col] = cst;
} else {
cost[x][col] += cst;
}
}
dist2[x] = 1e18;
}
priority_queue<tuple<ll, int, int>> q;
//cost, node, color
q.push(make_tuple(0, 0, 0));
dist2[0] = 0;
while(q.size() > 0){
int node;
ll cst;
int color;
tie(cst, node, color) = q.top();
cst *= -1;
q.pop();
if (node == n - 1 && color == 0){
break;
}
if (used[node].find(color) == used[node].end()){
used[node][color] = 1;
if (color != 0){
//we need to go to a node with the same color
for (auto con: cons[node]){
if (con.color == color){
if (used[con.d].find(0) == used[con.d].end()){
ll ncost = cst + cost[node][color] - con.cost;
if (dist2[con.d] > ncost){
dist2[con.d] = ncost;
q.push(make_tuple(-1 * ncost, con.d, 0));
}
}
}
}
}
else{
//there are 3 things which we can do
for (auto con: cons[node]){
//switch everything but the connection
ll ncost = cst + cost[node][con.color] - con.cost;
if (dist2[con.d] > ncost){
dist2[con.d] = ncost;
q.push(make_tuple(-1 * ncost, con.d, 0));
}
//switch our node only
ncost = cst + con.cost;
if (dist2[con.d] > ncost){
dist2[con.d] = ncost;
q.push(make_tuple(-1 * ncost, con.d, 0));
}
//dont switch anything and make the next node switch
ncost = cst;
if (dist[con.d].find(con.color) == dist[con.d].end() || (dist[con.d][con.color] > ncost && ncost < dist2[con.d] && cost[con.d][con.color] > con.cost)){
dist[con.d][con.color] = ncost;
q.push(make_tuple(-1 * ncost, con.d, con.color));
}
}
}
}
}
if (dist2[n - 1] == 1e18){
cout << -1 << "\n";
}
else{
cout << dist2[n - 1] << "\n";
}
}