Submission #989072

#	Time	Username	Problem	Language	Result	Execution time	Memory
989072		Celebi_276	Robot (JOI21_ho_t4)	C++17	100 / 100	689 ms	84412 KiB

Main

#include <bits/stdc++.h>
using namespace std;

#define      FILE   "TEST"
#define    all(v)   v.begin(), v.end()
#define   rall(v)   v.rbegin(), v.rend()
#define        fi   first
#define        se   second

const int MaxN = 1E5 + 15;
const long long INF = 9E18;

struct Edge {
    int to, c;
    long long d;
};

map <int, vector <Edge>> G[MaxN];
long long dp[MaxN];
map <int, long long> f[MaxN], sumd[MaxN];
map <int, vector <Edge>>::iterator it;

int n, m, u, v, c, d;
typedef tuple <long long, int, int> T;

signed main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL); cout.tie(NULL);

    if (fopen(FILE".INP", "r")) {
        freopen(FILE".INP", "r", stdin);
        freopen(FILE".OUT", "w", stdout);
    }

    cin >> n >> m;
    while (m--) {
        cin >> u >> v >> c >> d;

        G[u][c].push_back({v, c, d});
        G[v][c].push_back({u, c, d});

        sumd[u][c] += d;
        sumd[v][c] += d;
    }

    for (int i = 1; i <= n; i++) dp[i] = INF;
    dp[1] = 0;

    priority_queue <T> Q;
    Q.emplace(0, 1, 0);

    while (Q.size()) {
        long long w;
        int u, c;
        tie(w, u, c) = Q.top();
        Q.pop();

        if (c) {
            if (f[u][c] != -w) continue;
            for (Edge E : G[u][c]) {
                long long cost = sumd[u][c] - E.d - w;

                if (dp[E.to] > cost) {
                    dp[E.to] = cost;
                    Q.emplace(-dp[E.to], E.to, 0);
                }
            }
        }

        else {
            if (dp[u] != -w) continue;
            for (it = G[u].begin(); it != G[u].end(); it++)
                for (Edge E : it->second) {
                    long long cost;

                    cost = sumd[u][E.c] - E.d - w;
                    if (dp[E.to] > cost) {
                        dp[E.to] = cost;
                        Q.emplace(-dp[E.to], E.to, 0);
                    }

                    cost = E.d - w;
                    if (dp[E.to] > cost) {
                        dp[E.to] = cost;
                        Q.emplace(-dp[E.to], E.to, 0);
                    }

                    cost = -w;
                    if (!f[E.to].count(E.c) || f[E.to][E.c] > cost) {
                        f[E.to][E.c] = cost;
                        Q.emplace(-f[E.to][E.c], E.to, E.c);
                    }
                }
        }
    }
    
    cout << (dp[n] == INF ? -1 : dp[n]);

    return 0;
}

Compilation message (stderr)

Main.cpp: In function 'int main()':
Main.cpp:31:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   31 |         freopen(FILE".INP", "r", stdin);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
Main.cpp:32:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   32 |         freopen(FILE".OUT", "w", stdout);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~

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