Submission #1278639

#	Time	Username	Problem	Language	Result	Execution time	Memory
1278639		phuocrucpp	Robot (JOI21_ho_t4)	C++20	0 / 100	755 ms	80496 KiB

Main

/*ㅤ∧＿∧
　(　･∀･)
　(　つ┳⊃
ε (_)へ⌒ヽﾌ
 (　　(　･ω･)
 ◎―◎   ⊃  ⊃
BePhuongSuperuwi
From TK4 - CHT
ㅤㅤ／ ⌒＼____
　 /・　　 ）　　\
　/ノへ ノ　　　 /|
ノ　　  ＼\ |/_/_/*/

#include<bits/stdc++.h>
#define task "main"
#define endl '\n'
#define int int
#define pb push_back
#define int long long
#define fi first
#define se second
#define oo 1e18
#define ii pair<int,int>
using namespace std;
const int maxn = 1e6 + 5;
map<ii, int> sum;
map<ii, int> id;
int lim = 0, n, m;
int u[maxn], v[maxn], c[maxn];
int p[maxn];
int dist[maxn];
vector<ii> g[maxn];
void djk() {
    priority_queue <ii, vector <ii>, greater <ii>> q;

    for (int i = 1; i <= lim; i++) dist[i] = oo;
    dist[1] = 0;
    q.push({0, 1});

    while(!q.empty()) {
        int z = q.top().se, cost = q.top().fi;
        q.pop();
        if (cost > dist[z]) continue;

        for (auto e : g[z]) {
            int x = e.fi, y = e.se;
            if (dist[x] > dist[z] + y) {
                dist[x] = dist[z] + y;
                q.push({dist[x], x});
            }
        }
    }
    if (dist[n] == oo) cout << "-1";
    else cout << dist[n];
}
main() {
    ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
    if(fopen(task".inp","r")) {
        freopen(task".inp","r",stdin);
        freopen(task".out","w",stdout);
    }
    cin >> n >> m;
    for (int i = 1; i <= m; i++) cin >> u[i] >> v[i] >> c[i] >> p[i];

    for (int i = 1; i <= m; i++) {
        sum[{u[i], c[i]}] += p[i];
        sum[{v[i], c[i]}] += p[i];
    }

    lim = n;
    for (int i = 1; i <= m; i++) {
        ii ku = {u[i], c[i]};
        ii kv = {v[i], c[i]};
        if (!id.count(ku)) id[ku] = ++lim;
        if (!id.count(kv)) id[kv] = ++lim;

        int idu = id[ku], idv = id[kv];
        int sumu = sum[ku], sumv = sum[kv];
        g[u[i]].pb({v[i], min(p[i], sumu - p[i])});
        g[u[i]].pb({idu, sumu - p[i]});
        g[idu].pb({v[i], 0});

        g[v[i]].pb({u[i], min(p[i], sumv - p[i])});
        g[v[i]].pb({idv, sumv - p[i]});
        g[idv].pb({u[i], 0});
    }

    djk();
}

Compilation message (stderr)

Main.cpp:19: warning: "int" redefined
   19 | #define int long long
      | 
Main.cpp:17: note: this is the location of the previous definition
   17 | #define int int
      | 
Main.cpp:56:1: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
   56 | main() {
      | ^~~~
Main.cpp: In function 'int main()':
Main.cpp:59:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   59 |         freopen(task".inp","r",stdin);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~
Main.cpp:60:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   60 |         freopen(task".out","w",stdout);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~

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