oj.uz

Submission #446837

# Submission time Handle Problem Language Result Execution time Memory
446837 2021-07-23T12:38:43 Z gsc2001 Robot (JOI21_ho_t4) C++17
0 / 100
 450 ms 41984 KB 
#include <bits/stdc++.h>

using namespace std;
#define ll long long
#define ld long double
#define f(i, l, r) for (int i = l; i <= r; i++)
#define debug(x) cout << #x << '=' << (x) << endl
#define pb push_back
#define all(x) x.begin(), x.end()
#define sz(x) (ll)(x).size()
#define ff first
#define ss second

using PLL = pair<ll, ll>;
using VL = vector<ll>;
using VLL = vector<pair<ll, ll>>;

// -------------------------------------------------------------------------------
constexpr int mod = 1e9 + 7;

void setIO(const string &name = "") {
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    if (sz(name)) {
        freopen((name + ".in").c_str(), "r", stdin);
        freopen((name + ".out").c_str(), "w", stdout);
    }
}
// -------------------------------------------------------------------------------
// ------------------------Template End ------------------------------------------
// -------------------------------------------------------------------------------

struct Edge {
    ll color, changePrice, to;

    Edge(ll t, ll c, ll p) : color(c), changePrice(p), to(t) {

    }
};

int main() {
    setIO();
    ll n, m;
    cin >> n >> m;
    vector<vector<Edge>> adj(n);
    vector<map<ll, ll>> colorCount(n);
    ll a, b, c, p;
    for (int i = 0; i < m; i++) {
        cin >> a >> b >> c >> p;
        a--, b--;
        adj[a].push_back(Edge(b, c, p));
        adj[b].push_back(Edge(a, c, p));
        colorCount[a][c]++;
        colorCount[b][c]++;
    }

    priority_queue<pair<ll, ll>> pq;
    vector<ll> dist(n, 1e18);
    dist[0] = 0;

    pq.push({0, 0});

    ll distNow, node;
    while (!pq.empty()) {
        tie(distNow, node) = pq.top();
        distNow = -distNow;
        pq.pop();
        if (dist[node] != distNow) continue;

        for (auto edge: adj[node]) {
            ll len = 0;
            if (colorCount[node][edge.color] > 1) {
                len += edge.changePrice;
            }

            if (dist[node] + len < dist[edge.to]) {
                dist[edge.to] = dist[node] + len;
                pq.push({-dist[edge.to], edge.to});
            }
        }
    }

    if (dist[n - 1] == 1e18) {
        cout << "-1";
    }
    else cout << dist[n - 1];

    return 0;
}

Compilation message

Main.cpp: In function 'void setIO(const string&)':
Main.cpp:25:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   25 |         freopen((name + ".in").c_str(), "r", stdin);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
Main.cpp:26:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   26 |         freopen((name + ".out").c_str(), "w", stdout);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

Subtask #1
0 / 34.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 204 KB Output is correct
2 Correct 1 ms 204 KB Output is correct
3 Correct 1 ms 204 KB Output is correct
4 Correct 1 ms 204 KB Output is correct
5 Correct 1 ms 332 KB Output is correct
6 Correct 1 ms 312 KB Output is correct
7 Incorrect 1 ms 452 KB Output isn't correct
8 Halted 0 ms 0 KB -

Subtask #2
0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 102 ms 13948 KB Output is correct
2 Correct 33 ms 7100 KB Output is correct
3 Correct 107 ms 17748 KB Output is correct
4 Correct 59 ms 9888 KB Output is correct
5 Incorrect 450 ms 41984 KB Output isn't correct
6 Halted 0 ms 0 KB -

Subtask #3
0 / 42.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 204 KB Output is correct
2 Correct 1 ms 204 KB Output is correct
3 Correct 1 ms 204 KB Output is correct
4 Correct 1 ms 204 KB Output is correct
5 Correct 1 ms 332 KB Output is correct
6 Correct 1 ms 312 KB Output is correct
7 Incorrect 1 ms 452 KB Output isn't correct
8 Halted 0 ms 0 KB -