Submission #477999

#TimeUsernameProblemLanguageResultExecution timeMemory
477999sumit_kk10Ferries (NOI13_ferries)C++17
0 / 40
270 ms62888 KiB
#include <bits/stdc++.h> #define fast ios_base::sync_with_stdio(0);cin.tie(NULL);cout.tie(NULL) #define ll long long int #define ld long double using namespace std; const int N = 1e6 + 5; const int MOD = 1e9 + 7; vector<int> inc[N], graph[N]; int n, m; vector<int> dis(N, INT_MAX); void dijsktra(int node){ priority_queue<pair<int, int>, vector<pair<int, int> >, greater<pair<int, int> > > pq; pq.push({0, node}); dis[node] = 0; while(!pq.empty()){ int cost = pq.top().first; int node = pq.top().second; pq.pop(); for(auto k : graph[node]){ if(dis[k] > cost + inc[k].back()){ dis[k] = cost + inc[k].back(); pq.push({dis[k], k}); } inc[k].pop_back(); } } } void solve(){ cin >> n >> m; for(int i = 1; i <= m; ++i){ int u, v, c; cin >> u >> v >> c; graph[v].push_back(u); inc[u].push_back(c); } for(int i = 1; i <= n; ++i) sort(inc[i].begin(), inc[i].end()); dijsktra(n); cout << dis[1] << "\n"; } int main(){ fast; int t = 1; // cin >> t; while(t--) solve(); return 0; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...