Pagini recente » Cod sursa (job #898582) | Cod sursa (job #3247316) | Cod sursa (job #1647339) | Cod sursa (job #641830) | Cod sursa (job #2299138)
#include <cmath>
#include <cstdio>
#include <queue>
#include <vector>
#define NMAX 1510
#define MOD 104659
using std::vector;
using std::priority_queue;
struct Arc {
int node;
long double cost;
};
inline bool operator<(Arc x, Arc y) {
return x.cost > y.cost;
}
int n, m;
vector<Arc> ad[NMAX];
int nr[NMAX];
long double dp[NMAX];
bool onPQ[NMAX];
priority_queue<Arc> pq;
inline bool equals(long double x, long double y) {
return (x < y ? y - x : x - y) < 1e-9L;
}
int main() {
int a, b, c;
freopen("dmin.in", "r", stdin);
freopen("dmin.out", "w", stdout);
scanf("%d %d\n", &n, &m);
for (int i = 0; i < m; i++) {
scanf("%d %d %d\n", &a, &b, &c);
ad[a].push_back({b, log((long double) c)});
ad[b].push_back({a, log((long double) c)});
if (a == 1)
nr[b] = 1;
else if (b == 1)
nr[a] = 1;
}
pq.push({1, 0});
onPQ[1] = true;
while (!pq.empty()) {
int node = pq.top().node;
pq.pop();
onPQ[node] = false;
for (Arc arc : ad[node]) {
long double cost = dp[node] + arc.cost;
if (equals(dp[arc.node], 0) || (cost < dp[arc.node] || equals(cost, dp[arc.node]))) {
dp[arc.node] = cost;
if (equals(cost, dp[arc.node]))
nr[arc.node] = (nr[arc.node] + nr[node]) % MOD;
else
nr[arc.node] = nr[node];
if (!onPQ[arc.node]) {
pq.push({arc.node, dp[arc.node]});
onPQ[arc.node] = true;
}
}
}
}
for (int i = 2; i <= n; i++)
printf("%d ", nr[i]);
printf("\n");
fclose(stdout);
return 0;
}