Submission #197522

#	Time	Username	Problem	Language	Result	Execution time	Memory
197522		handlename	Ferries (NOI13_ferries)	C++17	40 / 40	325 ms	18908 KiB

ferries

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