Submission #379798

#	Time	Username	Problem	Language	Result	Execution time	Memory
379798		TeaTime	Robot (JOI21_ho_t4)	C++17	34 / 100	3075 ms	113236 KiB

Main

#include <iostream>
#include <vector>
#include <algorithm>
#include <bitset>
#include <set>
#include <map>
#include <string>
#include <cmath>
#include <ctime>
#include <queue>
 
using namespace std;
 
typedef long long ll;
typedef long double ld;
#define fastInp cin.tie(0); cout.tie(0); ios_base::sync_with_stdio(0);
 
const ll  MOD = 1e9 + 7, MX2 = 1e6, SZ = 1e6 + 100, INF = 1e9 * 1e9 + 100;
 
ll n, m;
 
struct edge {
    ll to, c, p, ind;
};
 
vector<vector<edge>> gr;
set<tuple<ll, ll, ll>> dists; // dist, v, col
map<pair<ll, ll>, ll> sv;
map<pair<ll, ll>, ll> cnt;
vector<map<ll, vector<ll>>> cols;
 
signed main() {
    fastInp;
 
    cin >> n >> m;
 
    gr.resize(n);
    cols.resize(n);
    dists.insert({ 0, 0, 0 });
    for (int i = 1; i < n; i++) dists.insert({ INF, i, 0 });
    for (int i = 0; i < m; i++) {
        ll u, v, c, p;
        cin >> u >> v >> c >> p;
        u--; v--;
        gr[u].push_back({ v, c, p, gr[v].size() });
        gr[v].push_back({ u, c, p, gr[u].size() - 1 });
        cols[u][c].push_back(gr[u].size() - 1);
        cols[v][c].push_back(gr[v].size() - 1);
        dists.insert({ INF, u, c });
        dists.insert({ INF, v, c });
        cnt[{v, c}] += p;
        cnt[{u, c}] += p;
    }
 
    for (auto c : dists) sv[{get<1>(c), get<2>(c)}] = get<0>(c);
     
    ll ds = INF;
    while (!dists.empty()) {
        tuple<ll, ll, ll> cur = (*dists.begin());
        dists.erase(dists.begin());
        ll d = get<0>(cur);
        ll v = get<1>(cur);
        ll c = get<2>(cur);
        if (v == n - 1 && c == 0) {
            ds = d;
            break;
        }
 
        if (c == 0) {
            for (auto e : gr[v]) {
                if (sv[{e.to, 0}] > d + e.p) {
                    dists.erase({ sv[{e.to, 0}], e.to, 0 });
                    sv[{e.to, 0}] = d + e.p;
                    dists.insert({ sv[{e.to, 0}], e.to, 0 });
                }
 
                if (sv[{e.to, 0}] > d + cnt[{v, e.c}] - e.p) {
                    dists.erase({ sv[{e.to, 0}], e.to, 0 });
                    sv[{e.to, 0}] = d + cnt[{v, e.c}] - e.p;
                    dists.insert({ sv[{e.to, 0}], e.to, 0 });
                }
            }
 
            for (auto e : gr[v]) {
                if (sv[{e.to, e.c}] > d) {
                    dists.erase({ sv[{e.to, e.c}], e.to, e.c });
                    sv[{e.to, e.c}] = d;
                    dists.insert({ sv[{e.to, e.c}], e.to, e.c });
                }
            }
        }
        else {
            for (auto ind : cols[v][c]) {
                edge e = gr[v][ind];
 
                if (sv[{e.to, 0}] > d + cnt[{v, e.c}] - e.p) {
                    dists.erase({ sv[{e.to, 0}], e.to, 0 });
                    sv[{e.to, 0}] = d + cnt[{v, e.c}] - e.p;
                    dists.insert({ sv[{e.to, 0}], e.to, 0 });
                }
            }
        }
    }
 
    ll a = ds;
 
    if (a == INF) {
        cout << "-1";
    }
    else {
        cout << a;
    }
 
    return 0;
}
 
/*
4 6
1 4 4 4
3 4 1 3
1 3 4 4
2 4 3 1
2 3 3 2
1 2 4 2
 
5 2
1 4 1 2
3 5 1 4
 
5 7
2 3 7 1
1 4 5 1
4 5 3 1
3 4 7 1
2 4 3 1
3 5 6 1
1 2 5 1
 
13 21
7 10 4 4
3 6 4 7
8 10 4 5
3 9 2 5
1 4 4 5
2 6 4 2
3 11 2 2
3 8 16 2
8 11 16 1
6 10 4 14
6 8 16 6
9 12 16 5
5 13 4 6
1 12 4 7
2 4 4 18
2 9 4 10
2 12 4 6
10 13 4 28
5 7 2 5
5 11 2 16
7 13 4 20
*/

Compilation message (stderr)

Main.cpp: In function 'int main()':
Main.cpp:45:46: warning: narrowing conversion of '(& gr.std::vector<std::vector<edge> >::operator[](((std::vector<std::vector<edge> >::size_type)v)))->std::vector<edge>::size()' from 'std::vector<edge>::size_type' {aka 'long unsigned int'} to 'll' {aka 'long long int'} [-Wnarrowing]
   45 |         gr[u].push_back({ v, c, p, gr[v].size() });
      |                                    ~~~~~~~~~~^~
Main.cpp:46:49: warning: narrowing conversion of '((& gr.std::vector<std::vector<edge> >::operator[](((std::vector<std::vector<edge> >::size_type)u)))->std::vector<edge>::size() - 1)' from 'std::vector<edge>::size_type' {aka 'long unsigned int'} to 'll' {aka 'long long int'} [-Wnarrowing]
   46 |         gr[v].push_back({ u, c, p, gr[u].size() - 1 });
      |                                    ~~~~~~~~~~~~~^~~

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