Pagini recente » Cod sursa (job #850232) | Cod sursa (job #1840398) | Cod sursa (job #1085204) | Cod sursa (job #941607) | Cod sursa (job #2258398)
#include <bits/stdc++.h>
#define DM 100005
#define pb push_back
#define INF 0x3f3f3f3f
#define ld long double
using namespace std;
ifstream fin("cameras.in");
ofstream fout("cameras.out");
struct mch{ int nod; int lg; };
struct elm{
int nod;
bool hasCamera;
ld time;
bool operator<(elm const& rhs) const{
if(time == rhs.time) {
if(hasCamera == rhs.hasCamera)
return nod<rhs.nod;
return hasCamera>rhs.hasCamera;
}
return time>rhs.time;
}
};
vector<mch>G[DM],G2[DM];
bitset<DM>hasCamera, viz;
int n,m,k,mx,limit,x,y,lg,totDist;
ld dist[DM], dist2[DM], ans;
priority_queue<elm>Q;
ld t(int km, bool isMax) {
ld ans = 0;
if(isMax) {
ans = 1.0*km/mx;
return ans;
}
ans = 1.0*km/limit;
return ans;
}
int main()
{
fin>>n>>m>>k;
for(int i=1;i<=k;++i){
fin>>x;
hasCamera[x]=1;
}
fin>>mx>>limit;
if(mx<limit) swap(mx, limit);
for(int i=1;i<=m;++i){
fin>>x>>y>>lg;
totDist += lg;
G[x].pb({y,lg});
G2[y].pb({x,lg});
}
if(k==1) {
ans = 1.0*totDist/mx;
fout<<setprecision(10)<<fixed<<ans;
return 0;
}
const ld toSet = INF;
fill(dist+1, dist+n+1, toSet);
fill(dist2+1, dist2+n+1, toSet);
Q.push({1, hasCamera[1], 0});
dist[1]=0;
while(!Q.empty()) {
elm next = Q.top();
//cout<<next.nod<<" "<<next.time<<'\n';
Q.pop();
if(viz[next.nod]) continue;
viz[next.nod] = 1;
for(auto mch: G[next.nod]){
double time = dist[next.nod] + t(mch.lg,!next.hasCamera);
if(time < dist[mch.nod]){
dist[mch.nod] = time;
Q.push({mch.nod, hasCamera[mch.nod]|next.hasCamera, time});
}
}
next.hasCamera |= hasCamera[next.nod];
}
ans = dist[n];
Q.push({n, hasCamera[n], 0});
viz.reset();
dist2[n] = 0;
while(!Q.empty()) {
elm next = Q.top();
Q.pop();
if(next.hasCamera || viz[next.nod]) continue;
viz[next.nod] = 1;
for(auto mch: G2[next.nod]){
double time = dist2[next.nod] + t(mch.lg,1);
if(hasCamera[mch.nod]) {
ans = min(ans, time + dist[mch.nod]);
} else if(time < dist2[mch.nod]){
dist2[mch.nod] = time;
Q.push({mch.nod, hasCamera[mch.nod]|next.hasCamera, time});
}
}
}
fout<<setprecision(10)<<fixed<<ans;
return 0;
}