Submission #732100

#	Time	Username	Problem	Language	Result	Execution time	Memory
732100		Trunkty	Ferries (NOI13_ferries)	C++14	40 / 40	293 ms	22412 KiB

ferries

#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 / 7
• Subtask 2: 10 / 10
• Subtask 3: 11 / 11
• Subtask 4: 12 / 12