oj.uz

Submission #830567

# Submission time Handle Problem Language Result Execution time Memory
830567 2023-08-19T08:06:16 Z RaresFelix Robot (JOI21_ho_t4) C++17
0 / 100
 242 ms 24680 KB 
#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 == (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;
        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

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

Subtask #1
0 / 34.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 5004 KB Output is correct
2 Correct 3 ms 4948 KB Output is correct
3 Correct 3 ms 5004 KB Output is correct
4 Correct 3 ms 4932 KB Output is correct
5 Correct 3 ms 5000 KB Output is correct
6 Correct 3 ms 5008 KB Output is correct
7 Incorrect 3 ms 5076 KB Output isn't correct
8 Halted 0 ms 0 KB -

Subtask #2
0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 87 ms 13680 KB Output is correct
2 Correct 40 ms 8808 KB Output is correct
3 Correct 137 ms 19384 KB Output is correct
4 Correct 72 ms 10848 KB Output is correct
5 Incorrect 242 ms 24680 KB Output isn't correct
6 Halted 0 ms 0 KB -

Subtask #3
0 / 42.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 5004 KB Output is correct
2 Correct 3 ms 4948 KB Output is correct
3 Correct 3 ms 5004 KB Output is correct
4 Correct 3 ms 4932 KB Output is correct
5 Correct 3 ms 5000 KB Output is correct
6 Correct 3 ms 5008 KB Output is correct
7 Incorrect 3 ms 5076 KB Output isn't correct
8 Halted 0 ms 0 KB -