Submission #1230165

#	Time	Username	Problem	Language	Result	Execution time	Memory
1230165		papaulo	Ferries (NOI13_ferries)	C++20	40 / 40	185 ms	14000 KiB

ferries

#include <bits/stdc++.h>
using namespace std;

#define MAXN 100100
int dist[MAXN];
int idx[MAXN];
vector<int> weights[MAXN];
vector<int> adjrev[MAXN];

#define RNG(i, n) for(int i=1;i<=n;i++)

int main() {
    cin.tie(nullptr);
    ios::sync_with_stdio(false);
    int n, m;
    cin >> n >> m;
    while(m--) {
        int a, b, c;
        cin >> a >> b >> c;
        weights[a].push_back(c);
        adjrev[b].push_back(a);
    }
    RNG(i, n) dist[i]=2e9;
    RNG(i, n) idx[i]=0;
    RNG(i, n) sort(weights[i].rbegin(), weights[i].rend());
    priority_queue<pair<int, int>> pq;
    dist[n]=0;
    pq.push({0, n});
    while(!pq.empty()) {
        auto pr=pq.top();
        pq.pop();
        int v=pr.second, d=dist[v];
        if(d<-pr.first) continue;
        for(auto u : adjrev[v]) {
            int newd=d+weights[u][idx[u]++];
            if(newd<dist[u]) {
                dist[u]=newd;
                pq.push({-newd, u});
            }
        }
    }
    cout << dist[1] << endl;
    return 0;
}

• Subtask 1: 7 / 7
• Subtask 2: 10 / 10
• Subtask 3: 11 / 11
• Subtask 4: 12 / 12