Submission #830602

#	Time	Username	Problem	Language	Result	Execution time	Memory
830602		RaresFelix	Robot (JOI21_ho_t4)	C++17	0 / 100	203 ms	20872 KiB

Main

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
const ll INF = 1e18;
const int MN = 100001;
int n, m;
struct Edge {
    int cul, cost, dest;
};
vector<Edge> L[MN];
vector<pair<int, ll> > G[MN]; /// nod, cost
ll Cost[MN];
int main() {
    cin >> n >> m;
    for(int i = 1; i <= m; ++i) {
        int u, v, c, w; 
        cin >> u >> v >> c >> w;
        L[u].push_back({c, w, v});
        L[v].push_back({c, w, u});
    }
    for(int i = 1; i <= n; ++i) {
        sort(L[i].begin(), L[i].end(), [&](auto a, auto b) {
            return a.cul < b.cul;
        });
        for(int j = 0; j < L[i].size(); ++j) {
            if((j == 0 || L[i][j - 1].cul != L[i][j].cul) &&
                    (j == ((int)L[i].size() - 1) || L[i][j + 1].cul != L[i][j].cul)) {
                G[i].push_back(make_pair(L[i][j].dest, 0));
            } else {
                G[i].push_back(make_pair(L[i][j].dest, L[i][j].cost));
            }
        }
    }
    priority_queue<pair<ll, int> > PQ;
    PQ.push(make_pair(0ll, 1));
    for(int i = 1; i <= n; ++i) Cost[i] = INF;
    Cost[1] = 0;
    
    while(!PQ.empty()) {
        ll nod = PQ.top().second, cost = - PQ.top().first;
        assert(cost >= 0);
        PQ.pop();
        if(Cost[nod] != cost) continue;
        for(auto [it, w] : G[nod]) {
            if(Cost[it] > Cost[nod] + w) {
                Cost[it] = Cost[nod] + w;
                PQ.push(make_pair(-Cost[it], it));
            }
        }
    }
    if(Cost[n] == INF) {
        cout << "-1\n";
    }  else {
        cout << Cost[n] << "\n";
    }
    return 0;
}

Compilation message (stderr)

Main.cpp: In function 'int main()':
Main.cpp:25:26: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<Edge>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   25 |         for(int j = 0; j < L[i].size(); ++j) {
      |                        ~~^~~~~~~~~~~~~

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