oj.uz

답안 #751834

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
751834 2023-06-01T14:54:15 Z Kihihihi Robot (JOI21_ho_t4) C++17
24 / 100
 1266 ms 92684 KB 
#include <iostream>
#include <iomanip>
#include <algorithm>
#include <numeric>
#include <cmath>
#include <cassert>
#include <ctime>
#include <chrono>
#include <cstdio>
#include <random>
#include <vector>
#include <string>
#include <map>
#include <unordered_map>
#include <set>
#include <unordered_set>
#include <deque>
#include <queue>
#include <bitset>
#include <list>
#include <fstream>
#include <functional>
#include <complex>
using namespace std;
mt19937_64 rnd(chrono::steady_clock::now().time_since_epoch().count());

short skip_cin = 0;
const long long INF = 1e18, MOD = 1e9 + 7, MOD2 = 998244353, LOG = 18;
const long double EPS = 1e-9, PI = acos(-1);

struct edge
{
    long long to, p;
};

long long n;
map<long long, vector<edge>> g[100000];
map<long long, long long> sume[100000], dist[100000];

void solve()
{
    long long m;
    cin >> n >> m;
    for (long long i = 0; i < m; i++)
    {
        long long a, b, c, p;
        cin >> a >> b >> c >> p;
        a--; b--;
        g[a][c].push_back({ b, p });
        g[b][c].push_back({ a, p });
    }
    for (long long v = 0; v < n; v++)
    {
        dist[v][0] = INF;
        for (auto& i : g[v])
        {
            for (auto& j : i.second)
            {
                dist[j.to][i.first] = INF;
                sume[v][i.first] += j.p;
            }
        }
    }

    dist[0][0] = 0;
    set<tuple<long long, long long, long long>> q = { { 0, 0, 0 } };
    while (q.size())
    {
        auto [d, v, pc] = *q.begin();
        q.erase(q.begin());

        if (pc != 0)
        {
            long long del = 0;
            for (auto& i : g[v][pc])
            {
                if (dist[i.to][0] + i.p == d)
                {
                    del = max(del, i.p);
                }
            }

            for (auto& i : g[v][pc])
            {
                long long add = sume[v][pc] - del - i.p;
                if (add < 0)
                {
                    continue;
                }
                if (d + add < dist[i.to][0])
                {
                    q.erase({ dist[i.to][0], i.to, 0 });
                    dist[i.to][0] = d + add;
                    q.insert({ dist[i.to][0], i.to, 0 });
                }
            }
            continue;
        }

        for (auto& [col, adj] : g[v])
        {
            for (auto& i : adj)
            {
                if (d + i.p < dist[i.to][col])
                {
                    q.erase({ dist[i.to][col], i.to, col });
                    dist[i.to][col] = d + i.p;
                    q.insert({ dist[i.to][col], i.to, col });
                }

                long long add = min(i.p, sume[v][col] - i.p);
                if (d + add < dist[i.to][0])
                {
                    q.erase({ dist[i.to][0], i.to, 0 });
                    dist[i.to][0] = d + add;
                    q.insert({ dist[i.to][0], i.to, 0 });
                }
            }
        }
    }
    cout << (dist[n - 1][0] == INF ? -1 : dist[n - 1][0]) << "\n";
}

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    srand(time(NULL));

    int tst = 1;
    //cin >> tst;
    while (tst--)
    {
        solve();
    }

    return 0;
}

/*
<3 <3 <3 <3 <3 <3 <3 <3 <3 <3 <3 <3 <3
⠀⠀⠀⠀⠀⠀⠀⠀⠀⣠⠤⠖⠚⢉⣩⣭⡭⠛⠓⠲⠦⣄⡀⠀⠀⠀⠀⠀⠀⠀
⠀⠀⠀⠀⠀⠀⢀⡴⠋⠁⠀⠀⠊⠀⠀⠀⠀⠀⠀⠀⠀⠀⠉⠳⢦⡀⠀⠀⠀⠀
⠀⠀⠀⠀⢀⡴⠃⢀⡴⢳⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠙⣆⠀⠀⠀
⠀⠀⠀⠀⡾⠁⣠⠋⠀⠈⢧⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠈⢧⠀⠀
⠀⠀⠀⣸⠁⢰⠃⠀⠀⠀⠈⢣⡀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠈⣇⠀
⠀⠀⠀⡇⠀⡾⡀⠀⠀⠀⠀⣀⣹⣆⡀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⢹⠀
⠀⠀⢸⠃⢀⣇⡈⠀⠀⠀⠀⠀⠀⢀⡑⢄⡀⢀⡀⠀⠀⠀⠀⠀⠀⠀⠀⠀⢸⡇
⠀⠀⢸⠀⢻⡟⡻⢶⡆⠀⠀⠀⠀⡼⠟⡳⢿⣦⡑⢄⠀⠀⠀⠀⠀⠀⠀⠀⢸⡇
⠀⠀⣸⠀⢸⠃⡇⢀⠇⠀⠀⠀⠀⠀⡼⠀⠀⠈⣿⡗⠂⠀⠀⠀⠀⠀⠀⠀⢸⠁
⠀⠀⡏⠀⣼⠀⢳⠊⠀⠀⠀⠀⠀⠀⠱⣀⣀⠔⣸⠁⠀⠀⠀⠀⠀⠀⠀⢠⡟⠀
⠀⠀⡇⢀⡇⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠠⠀⡇⠀⠀⠀⠀⠀⠀⠀⠀⢸⠃⠀
⠀⢸⠃⠘⡇⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⢸⠁⠀⠀⢀⠀⠀⠀⠀⠀⣾⠀⠀
⠀⣸⠀⠀⠹⡄⠀⠀⠈⠁⠀⠀⠀⠀⠀⠀⠀⡞⠀⠀⠀⠸⠀⠀⠀⠀⠀⡇⠀⠀
⠀⡏⠀⠀⠀⠙⣆⠀⠀⠀⠀⠀⠀⠀⢀⣠⢶⡇⠀⠀⢰⡀⠀⠀⠀⠀⠀⡇⠀⠀
⢰⠇⡄⠀⠀⠀⡿⢣⣀⣀⣀⡤⠴⡞⠉⠀⢸⠀⠀⠀⣿⡇⠀⠀⠀⠀⠀⣧⠀⠀
⣸⠀⡇⠀⠀⠀⠀⠀⠀⠉⠀⠀⠀⢹⠀⠀⢸⠀⠀⢀⣿⠇⠀⠀⠀⠁⠀⢸⠀⠀
⣿⠀⡇⠀⠀⠀⠀⠀⢀⡤⠤⠶⠶⠾⠤⠄⢸⠀⡀⠸⣿⣀⠀⠀⠀⠀⠀⠈⣇⠀
⡇⠀⡇⠀⠀⡀⠀⡴⠋⠀⠀⠀⠀⠀⠀⠀⠸⡌⣵⡀⢳⡇⠀⠀⠀⠀⠀⠀⢹⡀
⡇⠀⠇⠀⠀⡇⡸⠁⠀⠀⠀⠀⠀⠀⠀⠀⠀⠙⠮⢧⣀⣻⢂⠀⠀⠀⠀⠀⠀⢧
⣇⠀⢠⠀⠀⢳⠇⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠈⡎⣆⠀⠀⠀⠀⠀⠘
⢻⠀⠈⠰⠀⢸⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠰⠘⢮⣧⡀⠀⠀⠀⠀
⠸⡆⠀⠀⠇⣾⠀⠀⠀⠀⠀⠀⠀⠀⠀⢠⠆⠀⠀⠀⠀⠀⠀⠀⠙⠳⣄⡀⢢⡀
<3 <3 <3 <3 <3 <3 <3 <3 <3 <3 <3 <3 <3
*/

Subtask #1
0 / 34.0

# 결과 실행 시간 메모리 Grader output
1 Correct 7 ms 14292 KB Output is correct
2 Correct 7 ms 14292 KB Output is correct
3 Correct 7 ms 14388 KB Output is correct
4 Correct 7 ms 14408 KB Output is correct
5 Correct 7 ms 14420 KB Output is correct
6 Correct 7 ms 14412 KB Output is correct
7 Correct 8 ms 14576 KB Output is correct
8 Correct 8 ms 14420 KB Output is correct
9 Correct 11 ms 15100 KB Output is correct
10 Correct 11 ms 15056 KB Output is correct
11 Correct 9 ms 14804 KB Output is correct
12 Incorrect 10 ms 14764 KB Output isn't correct
13 Halted 0 ms 0 KB -

Subtask #2
24.0 / 24.0

# 결과 실행 시간 메모리 Grader output
1 Correct 236 ms 36604 KB Output is correct
2 Correct 104 ms 26316 KB Output is correct
3 Correct 173 ms 31456 KB Output is correct
4 Correct 128 ms 29508 KB Output is correct
5 Correct 1266 ms 92684 KB Output is correct
6 Correct 937 ms 80584 KB Output is correct
7 Correct 414 ms 63008 KB Output is correct
8 Correct 410 ms 52120 KB Output is correct
9 Correct 447 ms 52284 KB Output is correct
10 Correct 403 ms 54024 KB Output is correct
11 Correct 154 ms 40012 KB Output is correct

Subtask #3
0 / 42.0

# 결과 실행 시간 메모리 Grader output
1 Correct 7 ms 14292 KB Output is correct
2 Correct 7 ms 14292 KB Output is correct
3 Correct 7 ms 14388 KB Output is correct
4 Correct 7 ms 14408 KB Output is correct
5 Correct 7 ms 14420 KB Output is correct
6 Correct 7 ms 14412 KB Output is correct
7 Correct 8 ms 14576 KB Output is correct
8 Correct 8 ms 14420 KB Output is correct
9 Correct 11 ms 15100 KB Output is correct
10 Correct 11 ms 15056 KB Output is correct
11 Correct 9 ms 14804 KB Output is correct
12 Incorrect 10 ms 14764 KB Output isn't correct
13 Halted 0 ms 0 KB -