#include "crocodile.h"
#include <bits/stdc++.h>
using namespace std;
vector<int> dp;
vector<vector<pair<int, int>>> graph;
vector<bool> visited;
int inf = 1e9+5;
struct info{
int node;
int start;
int dist;
bool operator< (const info& rhs) const {
return dist > rhs.dist;
}
};
void dijkstra(vector<int> ends){
priority_queue<info> pq;
for(int e : ends)
pq.push({e, e, 0}), dp[e] = 0;
while(!pq.empty()){
info p = pq.top();
pq.pop();
vector<pair<int, int>> adj = graph[p.node];
for(pair<int, int> a : adj){
if(dp[p.node] + a.second < dp[a.first]){
dp[a.first] = dp[p.node] + a.second;
pq.push({a.first, p.start, dp[a.first]});
}
}
}
}
int travel_plan(int N, int M, int R[][2], int L[], int K, int P[]){
dp.assign(N, inf);
visited.assign(N, 0);
graph.assign(N, vector<pair<int, int>>());
for(int i = 0; i < M; i++){
graph[R[i][0]].push_back({R[i][1], L[i]});
graph[R[i][1]].push_back({R[i][0], L[i]});
}
vector<int> ends;
unordered_map<int, bool> end;
for(int i = 0; i < K; i++)
ends.push_back(P[i]), end[P[i]] = true;
dijkstra(ends);
int curr = 0, ans = 0;
while(!end[curr]){
visited[curr] = 1;
vector<pair<int, int>> adj = graph[curr];
deque<pair<int, int>> dq;
for(pair<int, int> a : adj){
if(visited[a.first]) continue;
if(dq.empty()){
dq.push_back({dp[a.first] + a.second, a.first});
continue;
}
if((int) dq.size() == 1){
if(dp[a.first] + a.second < dq.back().first) dq.push_back({dp[a.first] + a.second, a.first});
else dq.push_front({dp[a.first] + a.second, a.first});
continue;
}
if(dp[a.first] + a.second < dq.back().first) dq.pop_front(), dq.push_back({dp[a.first] + a.second, a.first});
else if(dp[a.first] + a.second < dq.front().first) dq.pop_front(), dq.push_front({dp[a.first] + a.second, a.first});
}
curr = dq.front().second;
ans += dq.front().first - dp[dq.front().second];
}
return ans;
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
0 ms |
212 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
0 ms |
212 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
0 ms |
212 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
