#include<bits/stdc++.h>
#include "crocodile.h"
#define pb push_back
#define x first
#define y second
using namespace std;
typedef long long ll;
typedef pair<int, int> ii;
const int maxn = 1e5 + 5;
const ll inf = 1e18;
int n, m, k;
vector<pair<int, ll>> adj[maxn];
int E[maxn];
pair<ll, ll> dist[maxn];
int solve() {
set<pair<pair<ll, ll>, int>> s;
for(int i = 0;i < n;i++) dist[i] = {inf, inf}, s.insert({dist[i], i});
for(int i = 0;i < n;i++) {
if(!E[i]) continue;
dist[i] = {0, 0};
s.erase({{inf, inf}, i});
s.insert({dist[i], i});
}
for(int i = 0;i < n;i++) {
//for(auto p : s) cout << "(" << p.y << " | " << p.x.x << " " << p.x.y << ")\n";
pair<pair<ll, ll>, int> state = *s.begin();s.erase(s.begin());
int x = state.y;
pair<ll, ll> d = state.x;
//cout << x << " -> " << d.x << ' ' << d.y << "\n";
//cout << "\n";
for(pair<int, ll> p : adj[x]) {
if(s.find({dist[p.x], p.x}) != s.end())
s.erase({dist[p.x], p.x});
pair<ll, ll> di = dist[p.x];
if(d.y + p.y < dist[p.x].y) {
dist[p.x].x = dist[p.x].y;
dist[p.x].y = d.y + p.y;
} else if(d.x + p.y < dist[p.x].x) {
dist[p.x].x = d.x + p.y;
}
if(di != dist[p.x]) s.insert({dist[p.x], p.x});
}
}
return (int)dist[0].x;
}
int travel_plan(int N, int M, int R[][2], int L[], int K, int P[])
{
n = N, m = M, k = K;
for(int i = 0;i < m;i++) {
adj[R[i][0]].pb({R[i][1], L[i]});
adj[R[i][1]].pb({R[i][0], L[i]});
}
for(int i = 0;i < k;i++) E[P[i]] = 1;
return solve();
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
2088 ms |
2636 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
2088 ms |
2636 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
2088 ms |
2636 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
