Submission #450485

#	Time	Username	Problem	Language	Result	Execution time	Memory
450485		SirCovidThe19th	Robot (JOI21_ho_t4)	C++14	0 / 100	1379 ms	81532 KiB

Main

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

#define ll long long

const int mx = 1e5+5;

int n, m; map<int, vector<tuple<int, int>>> adj[mx]; 
map<int, ll> tot[mx], dst[mx];
priority_queue<tuple<ll, int, int>> pq;

void add(int b, int c, int val){
    if (val < dst[b][c]) dst[b][c] = val, pq.push({-val, b, c});
}
int main(){
    cin >> n >> m;
    for (int i = 0; i < m; i++){
        int a, b, c, w; cin >> a >> b >> c >> w;
        adj[a][c].push_back({b, w});
        adj[b][c].push_back({a, w});
        tot[a][c] += w; tot[b][c] += w;
        dst[a][c] = dst[b][c] = dst[a][0] = dst[b][0] = LLONG_MAX;
    }dst[1][0] = 0; pq.push({0, 1, 0});
    while (!pq.empty()){
        ll cst; int A, C; tie(cst, A, C) = pq.top(); cst *= -1; pq.pop();
        if (cst != dst[A][C]) continue;
        if (C){
            for (auto [b, w] : adj[A][C])
                add(b, 0, tot[A][C] - w + cst);
        }else{
            for (auto c : adj[A]) for (auto [b, w] : c.second){ 
                add(b, 0, tot[A][c.first] - w + cst);
                add(b, 0, w + cst);
                add(b, c.first, cst);
            }
        }
    }cout<<(dst[n][0] == LLONG_MAX ? -1 : dst[n][0])<<endl;
}
 

Compilation message (stderr)

Main.cpp: In function 'int main()':
Main.cpp:28:23: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   28 |             for (auto [b, w] : adj[A][C])
      |                       ^
Main.cpp:31:45: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   31 |             for (auto c : adj[A]) for (auto [b, w] : c.second){
      |                                             ^

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