#include<bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace __gnu_pbds;
using namespace std;
typedef long long int ll;
typedef vector<ll> vi;
typedef vector<vector<ll>> vvi;
typedef pair<ll,ll> pi;
typedef map<ll,ll> mi;
typedef long double ld;
typedef vector<ld> vd;
typedef vector<vector<ld>> vvd;
typedef pair<ld,ld> pd;
#define ff first
#define ss second
#define srt(a) sort(a.begin(),a.end());
#define fip(k, n) for (ll i = k; i < n; i++)
#define fjp(k, n) for (ll j = k; j < n; j++)
#define fin(k, n) for (ll i = k; i >= n; i--)
#define fjn(k, n) for (ll j = k; j >= n; j--)
#define fp(k, n, m) for (ll k = n; k < m; k++)
#define fn(k, n, m) for (ll k = n; k >= m; k--)
#define ordered_set tree<pi, null_type,less< pi >, rb_tree_tag,tree_order_statistics_node_update>
#define totalOne(n) __builtin_popcount(n)
#define backZero(n) __builtin_ctzll(n)
#define frontZero(n) __builtin_clzll(n)
#define fx(k) for ( auto x : k )
#define test ll t;cin >> t;while (t--)
#define nli "\n"
// ==========================(debug)============================================================================================== //
#ifndef ONLINE_JUDGE
#define debug(x) cerr << #x <<" "; _printn(x); cerr << nli;
#else
#define debug(x)
#endif
void _printn(ll x){ cerr<<x<<" "; }
void _printn(int x){ cerr<<x<<" "; }
void _printn(ld x){ cerr<<x<<" "; }
void _printn(double x){ cerr<<x<<" "; }
void _printn(string x){ cerr<<x<<" "; }
void _printn(char x){ cerr<<x<<" "; }
void _printn(bool x){ cerr<<x<<" "; }
template<class T,class V>void _printn(pair<T,V> vv);
template<class T> void _printn(vector<T> vv);
template<class T> void _printn(set<T> vv);
template<class T,class V> void _printn(map<T,V> vv);
template<class T> void _printn(multiset<T> vv);
template<class T,class V>void _printn(pair<T,V> vv){ cerr<<"( ";_printn(vv.ff);cerr<<",";_printn(vv.ss);cerr<<")";}
template<class T> void _printn(vector<T> vv){ cerr<<"[ "; for(auto xx:vv){ _printn(xx);cerr<<" "; } cerr<<"]"; };
template<class T> void _printn(set<T> vv){ cerr<<"{ "; for(auto xx:vv){ _printn(xx);cerr<<" "; } cerr<<"}"; };
template<class T> void _printn(multiset<T> vv){ cerr<<"{ "; for(auto xx:vv){ _printn(xx);cerr<<" "; } cerr<<"}"; };
template<class T,class V> void _printn(map<T,V> vv){ cerr<<"{ "; for(auto xx:vv){ _printn(xx);cerr<<" "; } cerr<<"}"; };
// ==========================(debug)============================================================================================== //
ll n,m,tp,tp2,res,cnt,sum,tptp,ans;
const ll mx = 2e5+5;
const ll mod = 1e9+7;
// ==========================(MOD)=============================================================================================== //
ll mod_add(ll aa,ll bb){ return ((aa%mod)+(bb%mod))%mod; }
ll mod_minus(ll aa,ll bb){ return (((aa%mod)-(bb%mod))+10*mod)%mod; }
ll mod_mul(ll aa,ll bb){ return ((aa%mod)*(bb%mod))%mod; }
ll mod_power(ll aa,ll bb){ aa%=mod; ll empowered = 1; bb%=mod-1; while(bb > 0){ if(bb & 1) empowered = mod_mul(empowered,aa); bb = bb >> 1; aa = mod_mul(aa,aa); } return empowered; }
ll mod_divi(ll aa,ll bb){ aa=mod_mul(aa,mod_power(bb,mod-2)); return aa; }
// ==========================(MOD)=============================================================================================== //
bool f = false;
typedef struct edge
{
ll wet,des,tt,from;
void init(ll a,ll b,ll c,ll d){
wet = a;
des = b;
tt = c;
from = d;
return;
}
void deb(){
cerr<<wet<<" "<<des<<" "<<tt<<" "<<from<<nli;
return;
}
}ed;
ed ee;
class cmp{
public:
bool operator()(ed a,ed b){
return a.wet > b.wet;
}
};
vector<pi> adj[mx];
ll dis[mx][2],k;
ll to[mx][2];
bool mark[mx];
priority_queue<ed,vector<ed>,cmp> pq;
bool vis[mx];
void dfs(ll u){
vis[u] = 1;
// debug(u);
fx(adj[u]){
if(vis[x.ff])
continue;
if(to[u][1] == x.ff){
ans += x.ss;
dfs(x.ff);
}
}
}
int travel_plan(int N, int M, int R[][2], int L[], int K, int P[]){
n = N;
m = M;
fip(0,m){
adj[R[i][0]].push_back({R[i][1],L[i]});
adj[R[i][1]].push_back({R[i][0],L[i]});
}
// fip(0,n){
// debug(adj[i]);
// }
fip(0,n+2){
dis[i][0] = dis[i][1] = 1e18;
to[i][0] = to[i][1] = -100;
}
k = K;
fip(0,k){
tp = P[i];
mark[tp] = 1;
dis[P[i]][1] = dis[P[i]][0] = 0;
ee.init(0,tp,0,-100);
pq.push(ee);
}
while(pq.size()){
auto it = pq.top();
pq.pop();
// it.deb();
if(dis[it.des][it.tt] != it.wet){
continue;
}
to[it.des][it.tt] = it.from;
fx(adj[it.des]){
if(mark[x.ff])
continue;
if(dis[x.ff][0] > dis[it.des][it.tt] + x.ss){
if(dis[x.ff][1] > dis[x.ff][0] && dis[x.ff][0] != 1e18){
dis[x.ff][1] = dis[x.ff][0];
ee.init(dis[x.ff][0],x.ff,1,to[x.ff][0]);
pq.push(ee);
}
dis[x.ff][0] = dis[it.des][it.tt] + x.ss;
to[x.ff][0] = it.des;
}
else if(dis[x.ff][1] > dis[it.des][it.tt] + x.ss){
ee.init(dis[it.des][it.tt] + x.ss,x.ff,1,it.des);
pq.push(ee);
dis[x.ff][1] = dis[it.des][it.tt] + x.ss;
to[x.ff][1] = it.des;
}
}
}
// debug((int)pq.size());
// fip(0,n)
// cout<<to[i][0]<<" "<<to[i][1]<<nli;
// cout<<nli;
// fip(0,n)
// cout<<dis[i][0]<<" "<<dis[i][1]<<nli;
// fip(0,n+2)
// vis[i] = 0;
dfs(0);
return ans;
}
// int main(){
// ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0);
// #ifndef ONLINE_JUDGE
// freopen("input1.txt", "r", stdin);
// freopen("output1.txt", "w", stdout);
// freopen("error1.txt", "w", stderr);
// #endif // ONLINE_JUDGE
// int N,M,K;
// cin>>N>>M>>K;
// int R[M][2];
// int L[M];
// int P[K];
// fip(0,M){
// cin>>R[i][0]>>R[i][1];
// cin>>L[i];
// }
// fip(0,K)
// cin>>P[i];
// cout<<travel_plan(N,M,R,L,K,P)<<nli;
// cerr << "Time elapsed: " << setprecision(6) << 1000.0 * clock() / CLOCKS_PER_SEC << "ms\n";
// return 0;
// }
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
3 ms |
4948 KB |
Output is correct |
| 2 |
Correct |
3 ms |
4976 KB |
Output is correct |
| 3 |
Correct |
3 ms |
5024 KB |
Output is correct |
| 4 |
Correct |
5 ms |
5160 KB |
Output is correct |
| 5 |
Correct |
4 ms |
5164 KB |
Output is correct |
| 6 |
Correct |
3 ms |
5076 KB |
Output is correct |
| 7 |
Correct |
4 ms |
5204 KB |
Output is correct |
| 8 |
Correct |
4 ms |
5204 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
3 ms |
4948 KB |
Output is correct |
| 2 |
Correct |
3 ms |
4976 KB |
Output is correct |
| 3 |
Correct |
3 ms |
5024 KB |
Output is correct |
| 4 |
Correct |
5 ms |
5160 KB |
Output is correct |
| 5 |
Correct |
4 ms |
5164 KB |
Output is correct |
| 6 |
Correct |
3 ms |
5076 KB |
Output is correct |
| 7 |
Correct |
4 ms |
5204 KB |
Output is correct |
| 8 |
Correct |
4 ms |
5204 KB |
Output is correct |
| 9 |
Correct |
4 ms |
5460 KB |
Output is correct |
| 10 |
Correct |
3 ms |
5076 KB |
Output is correct |
| 11 |
Correct |
4 ms |
5160 KB |
Output is correct |
| 12 |
Correct |
9 ms |
5716 KB |
Output is correct |
| 13 |
Correct |
6 ms |
5844 KB |
Output is correct |
| 14 |
Correct |
3 ms |
5076 KB |
Output is correct |
| 15 |
Correct |
4 ms |
5288 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
3 ms |
4948 KB |
Output is correct |
| 2 |
Correct |
3 ms |
4976 KB |
Output is correct |
| 3 |
Correct |
3 ms |
5024 KB |
Output is correct |
| 4 |
Correct |
5 ms |
5160 KB |
Output is correct |
| 5 |
Correct |
4 ms |
5164 KB |
Output is correct |
| 6 |
Correct |
3 ms |
5076 KB |
Output is correct |
| 7 |
Correct |
4 ms |
5204 KB |
Output is correct |
| 8 |
Correct |
4 ms |
5204 KB |
Output is correct |
| 9 |
Correct |
4 ms |
5460 KB |
Output is correct |
| 10 |
Correct |
3 ms |
5076 KB |
Output is correct |
| 11 |
Correct |
4 ms |
5160 KB |
Output is correct |
| 12 |
Correct |
9 ms |
5716 KB |
Output is correct |
| 13 |
Correct |
6 ms |
5844 KB |
Output is correct |
| 14 |
Correct |
3 ms |
5076 KB |
Output is correct |
| 15 |
Correct |
4 ms |
5288 KB |
Output is correct |
| 16 |
Correct |
446 ms |
85900 KB |
Output is correct |
| 17 |
Correct |
77 ms |
24012 KB |
Output is correct |
| 18 |
Correct |
91 ms |
24480 KB |
Output is correct |
| 19 |
Correct |
552 ms |
94904 KB |
Output is correct |
| 20 |
Correct |
304 ms |
70404 KB |
Output is correct |
| 21 |
Correct |
43 ms |
12748 KB |
Output is correct |
| 22 |
Correct |
297 ms |
66992 KB |
Output is correct |
