oj.uz

Submission #38072

# Submission time Handle Problem Language Result Execution time Memory
38072 2017-12-31T17:36:00 Z nikhil Ferries (NOI13_ferries) C++14
40 / 40
 693 ms 21836 KB 
#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.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 9052 KB Output is correct
2 Correct 6 ms 9184 KB Output is correct
3 Correct 36 ms 10388 KB Output is correct
4 Correct 299 ms 21836 KB Output is correct
5 Correct 343 ms 21832 KB Output is correct

Subtask #2
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 9052 KB Output is correct
2 Correct 0 ms 9184 KB Output is correct
3 Correct 26 ms 10272 KB Output is correct
4 Correct 139 ms 15408 KB Output is correct
5 Correct 233 ms 16488 KB Output is correct

Subtask #3
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 39 ms 9980 KB Output is correct
2 Correct 39 ms 9976 KB Output is correct
3 Correct 556 ms 17636 KB Output is correct
4 Correct 633 ms 18092 KB Output is correct
5 Correct 549 ms 18072 KB Output is correct

Subtask #4
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 569 ms 17632 KB Output is correct
2 Correct 643 ms 17636 KB Output is correct
3 Correct 693 ms 19084 KB Output is correct
4 Correct 619 ms 19088 KB Output is correct
5 Correct 663 ms 19088 KB Output is correct