Archives
Trending
Support
Login
clear text
XML
Django
JavaScript
MATLAB
C
C++
C#
Python
SQL
Shell
Bash
Markdown
YAML
JSON
HTML
CSS
PHP
Java
Ruby
Go
Rust
Swift
Kotlin
Arduino
TypeScript
Perl
Autohotkey
Lua
SQF
R
Scala
Haskell
Groovy
Dart
Clojure
VB.NET
Objective-C
PowerShell
Bash
CoffeeScript
Verilog
#include
#include
#include
#include
using namespace std; const int maxn = 1e5 + 10; int n, m, k; int gas[maxn]; vector
graph[maxn]; struct node { int idx, passed, mood; node () {} node(int _idx, int _passed, int _mood) { idx = _idx; passed = _passed; mood = _mood; } bool operator < (const node & tmp) const { int score1 = 0, score2 = 0; if(mood > tmp.mood) { score1++; } else { score2++; } if(passed < tmp.passed) { score1++; } else { score2++; } return score1 < score2; } }; int main() { ios_base::sync_with_stdio(false); cin >> n >> m >> k; for(int i = 0; i < n; i++) { cin >> gas[i]; } for(int i = 0; i < m; i++) { int a, b; cin >> a >> b; a--; b--; graph[a].push_back(b); graph[b].push_back(a); } priority_queue
pq; pq.push(node(0, 1, gas[0])); vector
current_mood(n + 1, -2e9); int max_mood = -2e9, min_passing = 2e9; while(!pq.empty()) { node c = pq.top(); pq.pop(); if(c.idx == n - 1) { if(c.mood > max_mood) { max_mood = c.mood; min_passing = c.passed; } else if(c.mood == max_mood) { if(min_passing > c.passed) { min_passing = c.passed; } } continue; } for(int i = 0; i < (int) graph[c.idx].size(); i++) { int neighbour = graph[c.idx][i]; if(c.passed < k and current_mood[neighbour] < min(c.mood, gas[neighbour])) { pq.push(node(neighbour, c.passed + 1, min(c.mood, gas[neighbour]))); current_mood[neighbour] = min(c.mood, gas[neighbour]); } } } cout << max_mood << " " << min_passing << endl; return 0; }
Mark as private (unlisted)
for 30 minutes
for 6 hours
for 1 day
for 1 week
for 1 month
for 1 year
everlasting (like CCCP)