Submission #38894

#TimeUsernameProblemLanguageResultExecution timeMemory
38894cheater2kFerries (NOI13_ferries)C++14
0 / 40
586 ms13960 KiB
#include <bits/stdc++.h> using namespace std; const int N = 100005; const int inf = 1e9 + 10; typedef pair<int,int> ii; int n, m; vector<int> rev[N], len[N]; int d[N]; void solve() { for (int i = 1; i <= n; ++i) d[i] = inf; priority_queue < ii, vector<ii>, greater<ii> > pq; pq.push(ii(0, n)); d[n] = 0; while(!pq.empty()) { ii top = pq.top(); pq.pop(); int u = top.second, du = top.first; if (du != d[u]) continue; if (u == 1) { printf("%d\n", du); return; } for (int v : rev[u]) { if (!len[v].empty() && d[v] > d[u] + len[v].back()) { d[v] = d[u] + len[v].back(); len[v].pop_back(); pq.push(ii(d[v], v)); } } } } int main() { cin >> n >> m; while(m--) { int u, v, w; cin >> u >> v >> w; rev[v].push_back(u); len[u].push_back(w); } for (int i = 1; i <= n; ++i) { sort(len[i].begin(), len[i].end()); } solve(); }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...