oj.uz

Submission #830596

# Submission time Handle Problem Language Result Execution time Memory
830596 2023-08-19T08:15:41 Z RaresFelix Robot (JOI21_ho_t4) C++17
0 / 100
 200 ms 24600 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 == ((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;
        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: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.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 4948 KB Output is correct
2 Incorrect 2 ms 4948 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #2
0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 76 ms 13652 KB Output is correct
2 Correct 35 ms 8908 KB Output is correct
3 Correct 119 ms 19392 KB Output is correct
4 Correct 51 ms 10900 KB Output is correct
5 Incorrect 200 ms 24600 KB Output isn't correct
6 Halted 0 ms 0 KB -

Subtask #3
0 / 42.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 4948 KB Output is correct
2 Incorrect 2 ms 4948 KB Output isn't correct
3 Halted 0 ms 0 KB -