Pagini recente » Cod sursa (job #415658) | Cod sursa (job #1099265) | Cod sursa (job #490919) | Cod sursa (job #2910766) | Cod sursa (job #883373)
Cod sursa(job #883373)
#include<cstdio>
#include<vector>
#include<bitset>
#include<math.h>
#include<queue>
#include<algorithm>
using namespace std;
#define sh short int
#define NM 1001
#define KM 10001
#define MOD 1000000
#define pb push_back
#define INF 30000
vector<sh> timp[NM],capacitate[NM],nava[NM];
bitset<NM> special,viz;
vector<sh> low(NM,0),timpReal(NM,0),tata(NM,0);
vector<double> dep(NM,0);
sh sursa,dest,N,M,K;
sh navaPosibila[KM],tMinReal;
double tMinim;
inline sh minn(sh a, sh b) {
if (a<b) {
return a;
}
return b;
}
void puncteCritice(sh n) {
viz[n]=true;
low[n]=dep[n];
sh nrfii=0;
size_t g = nava[n].size();
for (size_t i=0; i<g; ++i) {
if (!viz[nava[n][i]]) {
++nrfii;
dep[nava[n][i]]=1+dep[n];
puncteCritice(nava[n][i]);
low[n]=minn(low[nava[n][i]],low[n]);
} else {
low[n]=minn(low[n],dep[nava[n][i]]);
}
}
if (n==sursa) {
special[sursa] = (nrfii!=1);
} else {
for (size_t i=0; i<g; ++i) {
if (low[nava[n][i]]>=dep[n]) {
special[n]=1;
break;
}
}
}
}
double timpMinim(sh cap) {
dep.assign(NM,INF);
low.assign(NM,INF);
queue<sh>q;
q.push(sursa);
dep[sursa] = 0;
low[sursa] = 0;
timpReal[sursa] = 1;
sh x,y;
while (!q.empty()) {
x=q.front();
q.pop();
size_t g = nava[x].size();
for (size_t i=0; i<g; ++i) {
double timpaux=log10f(timp[x][i]);
y=nava[x][i];
if (timpaux+dep[x]<dep[y] && (special[x] || (!special[x] && low[x]+capacitate[x][i]<=cap))) {
dep[y] = timpaux+dep[x];
tata[y]=x;
timpReal[y] = (timpReal[x] * timp[x][i] )%MOD;
if (special[nava[x][i]]) {
low[y] = 0;
} else {
low[y]=low[x]+capacitate[x][i];
}
q.push(y);
}
}
}
if (low[dest] > cap) {
return -1;
}
return dep[dest];
}
void afis(sh nod) {
if (tata[nod]){
afis(tata[nod]);
}
printf("%hd ",nod);
}
void cautCapacitateOptima() {
sh first=0,last=K-1,m,pok=navaPosibila[K-1];
while (first<=last) {
m=(first+last)>>1;
double dist=timpMinim(navaPosibila[m]);
if (dist<=tMinim && low[dest]<=navaPosibila[m]) {
pok=navaPosibila[m];
last=m-1;
tMinim=dist;
tMinReal=timpReal[dest];
} else {
first=m+1;
}
}
printf("%06d %d\n",tMinReal,pok);
timpMinim(pok);
afis(dest);
}
int main() {
freopen("misiune.in","r",stdin);
freopen("misiune.out","w",stdout);
scanf("%hd %hd %hd",&N,&M,&K);
scanf("%hd %hd",&sursa,&dest);
for (sh i=0; i<K; ++i) {
scanf("%hd",&navaPosibila[i]);
}
sort(navaPosibila,navaPosibila+K);
sh x,y,tmp,cap;
for (sh i=1; i<=M; ++i) {
scanf("%hd %hd %hd %hd",&x,&y,&tmp,&cap);
nava[x].pb(y);
timp[x].pb(tmp);
capacitate[x].pb(cap);
nava[y].pb(x);
timp[y].pb(tmp);
capacitate[y].pb(cap);
}
dep[sursa]=0;
puncteCritice(sursa);
tMinim=timpMinim(navaPosibila[K-1]);
tMinReal=timpReal[dest];
cautCapacitateOptima();
return 0;
}