Submission #38072

#	Time	Username	Problem	Language	Result	Execution time	Memory
38072		nikhil	Ferries (NOI13_ferries)	C++14	40 / 40	693 ms	21836 KiB

ferries

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

const int N = 1e5 + 2 ;
vector < pair < int, int > > adj[N], rev[N] ;
vector < int > edgeCosts[N] ;

int main()
{
    int n, m, u, v, c ; cin >> n >> m ;
    for(int i = 0; i < m; i++)
    {
        cin >> u >> v >> c ;
        // adj[u].push_back({v, c});
        rev[v].push_back({u, c});
        edgeCosts[u].push_back(c);
    }

    for(int i = 1; i <= n; i++)
        sort(edgeCosts[i].begin(), edgeCosts[i].end());

    int dist[n+1] ; for(int i = 0; i <= n; i++) dist[i] = 2e9 ;
    set < pair < int, int > > heap ; heap.insert({0, n});
    while(!heap.empty())
    {
        int top = (*heap.begin()).second, cst = (*heap.begin()).first ;
        heap.erase(heap.begin());
        for(auto grp : rev[top])
        {
            int cost = edgeCosts[grp.first].back() ;
            if((cst + cost) < dist[grp.first])
            {
                heap.erase({dist[grp.first], grp.first});
                dist[grp.first] = cst + cost ;
                heap.insert({dist[grp.first], grp.first});
            }
            edgeCosts[grp.first].pop_back();
        }
    }
    cout << dist[1] ;
    return 0;
}

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