Submission #889536

#	Time	Username	Problem	Language	Result	Execution time	Memory
889536		dwuy	Ferries (NOI13_ferries)	C++14	17 / 40	129 ms	21932 KiB

ferries

/// 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 / 7
• Subtask 2: 10 / 10
• Subtask 3: 0 / 11
• Subtask 4: 0 / 12