Pagini recente » Rezultatele filtrării | Borderou de evaluare (job #383850) | Cod sursa (job #2100248) | Borderou de evaluare (job #1353703) | Cod sursa (job #478621)
Cod sursa(job #478621)
#include<fstream>
#include<vector>
#include<cmath>
#include<algorithm>
#include<queue>
#define x first
#define y second
using namespace std;
const char iname[]="dmin.in";
const char oname[]="dmin.out";
const int maxn=1605;
const double inf=1e16;
const int mod=104569;
ifstream f(iname);
ofstream g(oname);
double eps=1e-8,dis[maxn];
inline int cmp(double a,double b)
{
if(a+eps<b)
return -1;
if(b+eps<a)
return 1;
return 0;
}
inline bool fcomp(int a,int b)
{
return dis[a]<dis[b];
}
int n,m,x,y,z,i,been[maxn],pos[maxn],a[maxn];
queue<int> Q;
vector<pair<int,double> > E[maxn];
int main()
{
f>>n>>m;
for(i=1;i<=m;++i)
f>>x>>y>>z,E[x].push_back(make_pair(y,log((double)z))),E[y].push_back(make_pair(x,log((double)z)));
for(i=1;i<=n;++i)
dis[i]=inf,been[i]=0;
dis[1]=0;
Q.push(1);
been[1]=1;
while(!Q.empty())
{
x=Q.front();
Q.pop();
been[x]=0;
for(vector<pair<int,double> >::iterator it=E[x].begin();it!=E[x].end();++it)
if(dis[x]+it->y<dis[it->x])
{
dis[it->x]=dis[x]+it->y;
if(been[it->x]==0)
been[it->x]=1,Q.push(it->x);
}
}
for(i=1;i<=n;++i)
pos[i]=i;
sort(pos+2,pos+n+1,fcomp);
a[1]=1;
for(i=2;i<=n;++i)
for(vector<pair<int,double> >::iterator it=E[pos[i]].begin();it!=E[pos[i]].end();++it)
if(cmp(dis[it->x]+it->y,dis[pos[i]])==0)
a[pos[i]]=(a[pos[i]]+a[it->x])%mod;
for(i=2;i<=n;++i)
g<<a[i]<<" ";
g<<"\n";
}