oj.uz

Submission #889536

# Submission time Handle Problem Language Result Execution time Memory
889536 2023-12-20T00:23:59 Z dwuy Ferries (NOI13_ferries) C++14
17 / 40
 129 ms 21932 KB 
/// dwuy: _,\,,,_\,__,\,,_
#include <bits/stdc++.h>

#define fastIO ios_base::sync_with_stdio(false); cin.tie(NULL)
#define file(a) freopen(a".inp","r",stdin); freopen(a".out", "w",stdout)
#define fi first
#define se second
#define endl "\n"
#define len(s) int32_t(s.length())
#define MASK(k)(1LL<<(k))
#define TASK ""

using namespace std;

typedef tuple<int, int, int> tpiii;
typedef pair<double, double> pdd;
typedef pair<int, int> pii;
typedef long long ll;

const long long OO = 1e18;
const int MOD = 1e9 + 7;
const int INF = 1e9;
const int MX = 100005;
int n, m;
int d[MX];
int rd[MX];
bitset<MX> vist;
vector<pii> G[MX];
vector<pii> rG[MX];

void fromNto1(){
    priority_queue<pii, vector<pii>, greater<pii>> Q;
    memset(rd, 0x3f, sizeof rd);
    Q.push({0, n});
    rd[n] = 0;
    while(Q.size()){
        int du, u;
        tie(du, u) = Q.top();
        Q.pop();
        if(du!=rd[u]) continue;
        for(pii &tmp: rG[u]){
            int v, c;
            tie(v, c) = tmp;
            if(rd[v] > rd[u] + c){
                rd[v] = rd[u] + c;
                Q.push({rd[v], v});
            }
        }
    }
}

vector<int> topo;
void dfs(int u){
    vist[u] = 1;
    for(pii &tmp: rG[u])if(!vist[tmp.fi]){
        dfs(tmp.fi);
    }
    topo.push_back(u);
}

int ferries(int N, int M, int A[], int B[], int C[]){
    n = N; m = M;
    for(int i=0; i<m; i++){
        int u, v, c;
        tie(u, v, c) = {A[i], B[i], C[i]};
        G[u].push_back({v, c});
        rG[v].push_back({u, c});
    }
    fromNto1();
    dfs(n);
    memset(d, 0x3f, sizeof d);
    d[1] = 0;
    for(int u: topo){
        vector<int> cost(G[u].size(), 0);
        vector<pii> node(G[u].size(), {0, 0});
        for(int i=0; i<(int)G[u].size(); i++){
            int v, c;
            tie(v, c) = G[u][i];
            cost[i] = c;
            node[i] = {rd[v], v};
        }
        sort(cost.begin(), cost.end(), greater<int>());
        sort(node.begin(), node.end());
        for(int i=0; i<(int)cost.size(); i++){
            int c = cost[i];
            int v = node[i].se;
            d[v] = min(d[v], d[u] + c);
        }
    }
    return d[n];
}

int a[MX*3], b[MX*3], c[MX*3];
int32_t main(){
    fastIO;
    //file(TASK);

    int n, m;
    cin >> n >> m;
    for(int i=0; i<m; i++){
        cin >> a[i] >> b[i] >> c[i];
    }
    cout << ferries(n, m, a, b, c);

    return 0;
}

Subtask #1
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 9308 KB Output is correct
2 Correct 2 ms 9400 KB Output is correct
3 Correct 8 ms 10180 KB Output is correct
4 Correct 86 ms 18876 KB Output is correct
5 Correct 78 ms 21932 KB Output is correct

Subtask #2
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 9048 KB Output is correct
2 Correct 2 ms 9308 KB Output is correct
3 Correct 8 ms 10264 KB Output is correct
4 Correct 37 ms 14032 KB Output is correct
5 Correct 53 ms 16472 KB Output is correct

Subtask #3
0 / 11.0

# Verdict Execution time Memory Grader output
1 Incorrect 11 ms 10588 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
0 / 12.0

# Verdict Execution time Memory Grader output
1 Incorrect 129 ms 21056 KB Output isn't correct
2 Halted 0 ms 0 KB -