//
// Created by adavy on 3/3/2023.
//
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using ld = long double;
using db = double;
using str = string;
using ii = pair<int,int>;
using pl = pair<ll,ll>;
using pd = pair<db,db>;
using vi = vector<int>;
using vb = vector<bool>;
using vl = vector<ll>;
using vd = vector<db>;
using vs = vector<str>;
using vii = vector<ii>;
using vpl = vector<pl>;
using vpd = vector<pd>;
#define tcT template<class T
#define tcTU tcT, class U
tcT> using V = vector<T>;
tcT, size_t SZ> using AR = array<T,SZ>;
tcT> using PR = pair<T,T>;
// pairs
#define mp make_pair
#define f first
#define s second
#define FOR(i,a,b) for (int i = (a); i < (b); ++i)
#define F0R(i,a) FOR(i,0,a)
#define ROF(i,a,b) for (int i = (b)-1; i >= (a); --i)
#define R0F(i,a) ROF(i,0,a)
#define trav(a,x) for (auto& a: x)
#define bg(x) begin(x)
#define all(x) bg(x), end(x)
#define rall(x) rbegin(x), rend(x)
#define sor(x) sort(all(x))
#define rsz resize
#define ins insert
#define ft front()
#define bk back()
#define pb push_back
#define eb emplace_back
#define pf push_front
const int MOD = 1e9+7; // 998244353;
const int MX = 2e5+5;
const ll INF = 1e18; // not too close to LLONG_MAX
const ld PI = acos((ld)-1);
const int dx[4] = {1,0,-1,0}, dy[4] = {0,1,0,-1}; // for every grid problem!!
#include "crocodile.h"
/*
#include <stdio.h>
#include <stdlib.h>
#define MAX_N 50000
#define MAX_M 10000000
static int N, M;
static int R[MAX_M][2];
static int L[MAX_M];
static int K;
static int P[MAX_N];
static int solution;
inline
void my_assert(int e) {if (!e) abort();}
void read_input()
{
int i;
my_assert(3==scanf("%d %d %d",&N,&M,&K));
for(i=0; i<M; i++)
my_assert(3==scanf("%d %d %d",&R[i][0],&R[i][1],&L[i]));
for(i=0; i<K; i++)
my_assert(1==scanf("%d",&P[i]));
my_assert(1==scanf("%d",&solution));
}*/
vl dist;
vl dist2;
vb vis;
vi par;
vector<vector<pair<ll,int>>> adj;
/*
void dfs(int nd){
vis[nd] = 1;
if (adj[nd].size() == 1){
dist[nd] = 0;
par[nd] = adj[nd][0].s;
return;
}
trav(nei, adj[nd]){ if (!vis[nei.s]) dfs(nei.s); else par[nd] = nei.s;}
ll bst = INF, sbst = INF;
for(auto&[len, nei]:adj[nd]){
if (nei == par[nd]) continue;
ll distN = dist[nei] + len;
if (distN < bst) {
sbst = bst; bst = distN;
}
else if (distN < sbst) {
sbst = distN;
}
}
dist[nd] = sbst;
}
*/
int travel_plan(int n, int m, int r[][2], int l[], int k, int p[])
{
adj.rsz(n);
vis.rsz(n);
dist.rsz(n);
dist2.rsz(n);
par.rsz(n);
fill(all(vis),0);
fill(all(dist),INF);
fill(all(dist2),INF);
F0R(i, k){
dist[p[i]] = 0;
dist2[p[i]] = 0;
}
F0R(i, m){
adj[r[i][0]].pb({l[i], r[i][1]});
adj[r[i][1]].pb({l[i], r[i][0]});
}
priority_queue<pair<ll, int>, vector<pair<ll, int>>, greater<pair<ll, int>>> hp;
F0R(i, k){ hp.push ({dist2[p[i]], p[i]});
}
while(!hp.empty()){
//cout << "sz" << " " << hp.size() << endl;
auto [cost, nd] = hp.top(); hp.pop();
vis[nd] = 1;
//cout << nd << " " << cost << endl;
//trav(i, dist) cout << i << " "; cout << endl;
//trav(i, dist2) cout << i << " "; cout << endl;
for (auto& [len, nei]:adj[nd]){
if (vis[nei]) continue;
ll distN = dist2[nd] + len;
if (distN < dist[nei]) {
dist2[nei] = dist[nei]; dist[nei] = distN;
if (dist2[nei] < INF) hp.push({dist2[nei],nei});
}
else if (distN < dist2[nei]) {
dist2[nei] = distN;
hp.push({dist2[nei],nei});
}
}
}
/*
dfs(0);
*/
return dist2[0];
}
/*
int main()
{
int ans;
read_input();
ans = travel_plan(N,M,R,L,K,P);
if(ans==solution)
printf("Correct.\n");
else
printf("Incorrect. Returned %d, Expected %d.\n",ans,solution);
return 0;
}*/
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
212 KB |
Output is correct |
| 2 |
Correct |
0 ms |
212 KB |
Output is correct |
| 3 |
Incorrect |
1 ms |
340 KB |
Output isn't correct |
| 4 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
212 KB |
Output is correct |
| 2 |
Correct |
0 ms |
212 KB |
Output is correct |
| 3 |
Incorrect |
1 ms |
340 KB |
Output isn't correct |
| 4 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
212 KB |
Output is correct |
| 2 |
Correct |
0 ms |
212 KB |
Output is correct |
| 3 |
Incorrect |
1 ms |
340 KB |
Output isn't correct |
| 4 |
Halted |
0 ms |
0 KB |
- |
