#include<bits/stdc++.h>
// #include "crocodile.h"
#define ll long long int
#define pb push_back
#define mp make_pair
#define FOR(i,n) for(i=0;i<(n);++i)
#define FORe(i,n) for(i=1;i<=(n);++i)
#define FORr(i,a,b) for(i=(a);i<(b);++i)
#define FORrev(i,n) for(i=(n);i>=0;--i)
#define ii pair<ll,ll>
#define vi vector<ll>
#define vii vector<ii>
#define ff first
#define ss second
#define cd complex<double>
#define vcd vector<cd>
#define ldd long double
#define dbgLine cout<<"Line : "<<__LINE__<<'\n'
#define all(x) (x).begin(),(x).end()
using namespace std;
/*
const short int __PRECISION = 10;
const ll MOD = 1e9+7;
const ll INF = 1e17 + 1101;
const ll LOGN = 17;
const ll MAXN = 2e5+5;
const ll ROOTN = 320;
const ldd PI = acos(-1);
const ldd EPS = 1e-7;
*/
struct edge
{
ll to, wt, ind;
inline void reset(){to = -1; wt = -1; ind = -1;}
inline void set(ll t, ll w, ll in){to = t; wt = w; ind = in;}
};
int travel_plan(int N,int M,int (* R)[2],int* L,int K,int* P)
{
vector<edge> g[N+1];
ll towards[N+1], i, d[N+1], d2[N+1];
bool open[M+K+1];
edge Neutral;
Neutral.reset();
FOR(i, N)
d[i] = d2[i] = 1e9 + 2;
d[N] = d2[N] = 0;
FOR(i, M)
{
g[R[i][0]].pb(Neutral);
g[R[i][1]].pb(Neutral);
g[R[i][0]][g[R[i][0]].size() - 1].set(R[i][1], L[i], i);
g[R[i][1]][g[R[i][1]].size() - 1].set(R[i][0], L[i], i);
open[i] = true;
}
FOR(i, K)
{
g[P[i]].pb(Neutral);
g[N].pb(Neutral);
g[P[i]][g[P[i]].size() - 1].set(N, 0, i + M);
g[N][g[N].size() - 1].set(P[i], 0, i + M);
open[i + M] = true;
}
set<ii> x; // (d,vertex);
x.insert(mp(0,N));
set<ii> :: iterator it;
while(!x.empty())
{
int a = (*(x.begin())).ss;
x.erase(x.begin());
for(edge pp : g[a])
{
if (d[pp.to] > d[a] + pp.wt)
{
x.erase(mp(d[pp.to],pp.to));
d[pp.to] = d[a] + pp.wt;
x.insert(mp(d[pp.to],pp.to));
towards[pp.to] = pp.ind;
}
}
}
FOR(i, N)
if(towards[i] < M)
open[towards[i]] = false;
// FOR(i, N)
// cout<<i<<" -> "<<((towards[i] < M) ? (R[towards[i]][0] + R[towards[i]][1] - i) : -1 )<<"\t d["<<i<<"] = "<<d[i]<<'\n';
x.clear();
x.insert(mp(0,N));
while(!x.empty())
{
// cout<<"x contains : "; for(ii vv : x) cout<<vv.ff<<' '<<vv.ss<<'\t'; cout<<endl;
int a = (*(x.begin())).ss;
x.erase(x.begin());
for(edge pp : g[a])
{
if (open[pp.ind] && d2[pp.to] > d2[a] + pp.wt)
{
// cout<<"updating "<<pp.to<<" from "<<a<<endl;
x.erase(mp(d2[pp.to],pp.to));
d2[pp.to] = d2[a] + pp.wt;
x.insert(mp(d2[pp.to],pp.to));
}
}
}
return d2[0];
}
/*
int main()
{
ios_base::sync_with_stdio(false);
cin.tie(NULL);
cout.tie(NULL);
int N, M, K, i;
cin>>N>>M>>K;
int R[M][2], L[M], P[K];
FOR(i, M) cin>>R[i][0]>>R[i][1]>>L[i];
FOR(i, K) cin>>P[i];
cout<<travel_plan(N,M,R,L,K,P);
return 0;
}
5 7 2
0 2 4
0 3 3
3 2 2
2 1 10
0 1 100
0 4 7
3 4 9
1 3
*/
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
4 ms |
384 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
4 ms |
384 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
4 ms |
384 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
