oj.uz

Submission #38073

# Submission time Handle Problem Language Result Execution time Memory
38073 2017-12-31T17:37:36 Z nikhil Ferries (NOI13_ferries) C++14
0 / 40
 509 ms 17636 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 ;
        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
0 / 7.0

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

Subtask #2
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 9052 KB Output is correct
2 Incorrect 3 ms 9184 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #3
0 / 11.0

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

Subtask #4
0 / 12.0

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