oj.uz

Submission #732100

# Submission time Handle Problem Language Result Execution time Memory
732100 2023-04-28T11:53:22 Z Trunkty Ferries (NOI13_ferries) C++14
40 / 40
 293 ms 22412 KB 
#include <bits/extc++.h>
using namespace std;
typedef long long ll;
#define int ll

int n,m;
vector<int> roads[100005],rev[100005];
int best[100005];
bool check[100005];

signed main(){
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
    cin >> n >> m;
    for(int i=1;i<=m;i++){
        int a,b,c;
        cin >> a >> b >> c;
        roads[a].push_back(c);
        rev[b].push_back(a);
    }
    for(int i=1;i<=n;i++){
        best[i] = 2e9;
        sort(roads[i].begin(),roads[i].end());
    }
    best[n] = 0;
    priority_queue<vector<int>,vector<vector<int>>,greater<vector<int>>> pq;
    pq.push({0,n});
    while(pq.size()>0){
        while(pq.size()>0 and check[pq.top()[1]]){
            pq.pop();
        }
        if(pq.size()==0){
            break;
        }
        int x = pq.top()[1];
        pq.pop();
        check[x] = true;
        for(int i:rev[x]){
            if(best[x]+roads[i].back()<best[i]){
                best[i] = best[x]+roads[i].back();
                pq.push({best[i],i});
            }
            roads[i].pop_back();
        }
    }
    cout << best[1] << "\n";
	return 0;
}

Subtask #1
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 4948 KB Output is correct
2 Correct 4 ms 5164 KB Output is correct
3 Correct 11 ms 6740 KB Output is correct
4 Correct 129 ms 22128 KB Output is correct
5 Correct 142 ms 22144 KB Output is correct

Subtask #2
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 4948 KB Output is correct
2 Correct 4 ms 5032 KB Output is correct
3 Correct 13 ms 6740 KB Output is correct
4 Correct 61 ms 13504 KB Output is correct
5 Correct 118 ms 14932 KB Output is correct

Subtask #3
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 16 ms 6536 KB Output is correct
2 Correct 18 ms 6480 KB Output is correct
3 Correct 219 ms 20608 KB Output is correct
4 Correct 278 ms 20992 KB Output is correct
5 Correct 287 ms 20252 KB Output is correct

Subtask #4
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 226 ms 20552 KB Output is correct
2 Correct 231 ms 20592 KB Output is correct
3 Correct 293 ms 22388 KB Output is correct
4 Correct 260 ms 22412 KB Output is correct
5 Correct 279 ms 22412 KB Output is correct