Submission #140341

#TimeUsernameProblemLanguageResultExecution timeMemory
140341nhc7502날다람쥐 (JOI14_ho_t4)C++14
25 / 100
867 ms9192 KiB
///EVERYONE BELIEVE IN GODTAEGYU #include<bits/stdc++.h> using namespace std; const long long MOD = 1000000; int n, m, i, j, k; int x, h[100141]; vector<pair<int,int>>graph[100141]; unordered_map<long long, int>dist; priority_queue<pair<int,pair<int,int>>>pq; inline pair<int,int> lltop(long long x) { return {x/MOD, x%MOD}; } inline long long ptoll(pair<int,int> x) { return x.first * MOD + x.second; } void f(int tree, int godo, int thist) { if(dist.find(ptoll({tree, godo})) == dist.end()) { dist[ptoll({tree, godo})] = thist; pq.push({thist, {tree, godo}}); } else if(dist[ptoll({tree, godo})] > thist) { dist[ptoll({tree, godo})] = thist; pq.push({thist, {tree, godo}}); } } int main(){ iostream::sync_with_stdio(0);cin.tie(0);cout.tie(0); for(cin>>n>>m>>x; i<n;) { cin>>h[++i]; } for(;m--;) { cin>>i>>j>>k; if(h[i] >= k) graph[i].push_back({j, k}); if(h[j] >= k) graph[j].push_back({i, k}); } dist[ptoll({1, x})] = 0; pq.push({0,{1,x}}); while(!pq.empty()) { x = pq.top().first; tie(m, i) = pq.top().second; pq.pop(); if(dist[ptoll({m, i})] != x) continue; for(auto next : graph[m]) { //m = 현재 나무, i = 현재 높이, j = 다음 나무, k = 다음 나무 거리 tie(j, k) = next; if(i < k) f(j, 0, x + k - i + k); else if(i - k > h[j]) f(j, h[j], x + i - h[j]); else f(j, i - k, x + k); } if(m == n) f(n, h[n], x + h[n] - i); } if(dist.find(ptoll({n, h[n]})) == dist.end()) cout<<-1; else cout<<dist[ptoll({n,h[n]})]; return 0; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...