Cod sursa(job #2258398)

Utilizator sergiudnyTritean Sergiu sergiudny Data 11 octombrie 2018 12:40:45
Problema Algoritmul lui Dijkstra Scor 0
Compilator cpp Status done
Runda Arhiva educationala Marime 2.62 kb
#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;
}