#include <bits/stdc++.h>
using namespace std;
void fast(){ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);}
//const int NN=1e5;
const long long INF=1e18;
// int R[NN+1][2], L[NN+1], P[NN+1];
int travel_plan(int N, int M, int R[][2], int L[], int K, int P[]){
vector<pair<int,int>> v[N];
for(int i=0; i<M; i++){
v[R[i][0]].push_back({R[i][1], L[i]});
v[R[i][1]].push_back({R[i][0], L[i]});
}
vector<vector<long long>> dist(N+2, vector<long long>(2, INF));
priority_queue<pair<long long,int>, vector<pair<long long,int>>, greater<pair<long long,int>>> pq;
for(int i=0; i<K; i++){
dist[P[i]][0]=dist[P[i]][1]=0;
pq.push({0, P[i]});
}
while(!pq.empty()){
auto[d, u]=pq.top(); pq.pop();
if(d>dist[u][1]) continue;
for(auto [to, di]:v[u]){
if(d+di<dist[to][1]){
dist[to][1]=d+di;
sort(dist[to].begin(), dist[to].end());
pq.push({d+di, to});
}
}
}
return dist[0][1];
}
// int main(){
// fast();
// int n, m, k; cin>>n>>m>>k;
// for(int i=0; i<m; i++){
// cin>>R[i][0]>>R[i][1];
// }
// for(int i=0; i<m; i++) cin>>L[i];
// for(int i=0; i<k; i++) cin>>P[i];
// cout<<travel_plan(n, m, k);
// }
/*
#define int long long
const int INF=1e18;
signed main(){
fast();
int teskes; cin>>teskes;
while(teskes--){
int n, m, k; cin>>n>>m>>k;
int a[n+1], now=0;
for(int i=1; i<=n; i++) cin>>a[i];
vector<pair<int,int>> v[n+1], to(2*k+5);
vector<int> dp(2*k+5, -INF);
dp[0]=0;
v[1].push_back({1, now++});
for(int i=1; i<=k; i++){
int a, b, c, d, h; cin>>a>>b>>c>>d>>h;
v[a].push_back({b, now++});
v[c].push_back({d, now++});
to[now-2]={now-1, h};
}
v[n].push_back({m, now});
for(int i=1; i<=n; i++){
int sz=v[i].size();
sort(v[i].begin(), v[i].end());
for(int j=1; j<sz; j++){
dp[v[i][j].second]=max(dp[v[i][j].second], dp[v[i][j-1].second]-(v[i][j].first-v[i][j-1].first)*a[i]);
}
for(int j=sz-2; j>=0; j--){
dp[v[i][j].second]=max(dp[v[i][j].second], dp[v[i][j+1].second]-(v[i][j+1].first-v[i][j].first)*a[i]);
}
for(auto [r, num]:v[i]){
if(to[num].first && dp[num]!=-INF){
dp[to[num].first]=max(dp[to[num].first], dp[num]+to[num].second);
}
}
}
if(dp[now]==-INF) cout<<"NO ESCAPE";
else cout<<-dp[now];
cout<<'\n';
}
}
*/
/*
#define int long long
const int INF=1e18, N=3e5;
signed main(){
fast();
int teskes; cin>>teskes;
while(teskes--){
int n, m, k; cin>>n>>m>>k;
int a[n+1], num=2;
for(int i=1; i<=n; i++) cin>>a[i];
map<pair<int,int>, int> mp; mp[{1, 1}]=0, mp[{n, m}]=1;
vector<pair<int,int>> v[N+1];
priority_queue<pair<int,int>, vector<pair<int,int>>, greater<pair<int,int>>> pq;
pq.push({1, 1}), pq.push({n, m});
for(int i=1; i<=k; i++){
int p, q, r, s, h; cin>>p>>q>>r>>s>>h;
if(!mp.count({p, q})) mp[{p, q}]=num++;
if(!mp.count({r, s})) mp[{r, s}]=num++;
v[mp[{p, q}]].push_back({mp[{r, s}], -h});
pq.push({p, q});
pq.push({r, s});
}
int la=pq.top().first, lb=pq.top().second; pq.pop();
while(!pq.empty()){
auto[na, nb]=pq.top(); pq.pop(); //new
if(la==na && lb==nb) continue;
if(la==na){
v[mp[{la, lb}]].push_back({mp[{na, nb}], (nb-lb)*a[la]});
v[mp[{na, nb}]].push_back({mp[{la, lb}], (nb-lb)*a[la]});
}
la=na, lb=nb;
}
vector<int> dist(num, INF);
vector<bool> vis(num);
dist[0]=0;
pq.push({0, 0});
while(!pq.empty()){
auto[d, u]=pq.top(); pq.pop();
if(vis[u]) continue;
vis[u]=true;
cout<<d<<' '<<u<<'\n';
for(auto &[to, h]:v[u]){
if(!vis[to] && dist[u]+h<dist[to]){
dist[to]=dist[u]+h;
pq.push({dist[to], to});
}
}
}
cout<<'\n';
for(auto [x, y]:mp) cout<<x.first<<' '<<x.second<<' '<<y<<'\n';
cout<<'\n';
// for(auto [x, y]:mp){
// cout<<x.first<<' '<<x.second<<" : ";
// for(auto [node, val]:v[y]) cout<<node<<' ';
// cout<<'\n';
// }
// if(dist[1]==INF) cout<<"NO ESCAPE";
// else cout<<dist[1];
// cout<<'\n';
}
}*/
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
4444 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
4444 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
4444 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
