oj.uz

Submission #197522

# Submission time Handle Problem Language Result Execution time Memory
197522 2020-01-21T13:31:18 Z handlename Ferries (NOI13_ferries) C++17
40 / 40
 325 ms 18908 KB 
#include <bits/stdc++.h>
using namespace std;
int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    vector<int> adjlist[100001];//node
    priority_queue<int> weights[100001];
    int n,m;
    cin>>n>>m;
    for (int i=0;i<m;i++){
        int a,b,c;
        cin>>a>>b>>c;
        adjlist[b].push_back(a);
        weights[a].push(c);
    }
    priority_queue<pair<int,int>,vector<pair<int,int> >,greater<pair<int,int> > >pq;
    int dist[100001];
    memset(dist,-1,sizeof(dist));
    pq.push(make_pair(0,n));
    dist[n]=0;
    while (!pq.empty()){
        pair<int,int> c=pq.top();
        pq.pop();
        if (c.first!=dist[c.second]) continue;
        for (auto curnode:adjlist[c.second]){
            int w=weights[curnode].top();
            weights[curnode].pop();
            if (dist[curnode]==-1 || dist[curnode]>c.first+w){
                dist[curnode]=c.first+w;
                pq.push(make_pair(dist[curnode],curnode));
            }
        }
    }
    cout<<dist[1];
}

Subtask #1
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 6268 KB Output is correct
2 Correct 9 ms 6392 KB Output is correct
3 Correct 18 ms 7416 KB Output is correct
4 Correct 144 ms 17496 KB Output is correct
5 Correct 143 ms 17384 KB Output is correct

Subtask #2
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 6136 KB Output is correct
2 Correct 8 ms 6264 KB Output is correct
3 Correct 18 ms 7420 KB Output is correct
4 Correct 69 ms 11804 KB Output is correct
5 Correct 121 ms 14712 KB Output is correct

Subtask #3
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 25 ms 7288 KB Output is correct
2 Correct 29 ms 7316 KB Output is correct
3 Correct 287 ms 18056 KB Output is correct
4 Correct 313 ms 18152 KB Output is correct
5 Correct 297 ms 17400 KB Output is correct

Subtask #4
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 273 ms 18044 KB Output is correct
2 Correct 270 ms 17996 KB Output is correct
3 Correct 314 ms 18908 KB Output is correct
4 Correct 317 ms 18844 KB Output is correct
5 Correct 325 ms 18616 KB Output is correct