Pagini recente » Cod sursa (job #2424549) | Cod sursa (job #2958546) | Cod sursa (job #444899) | Cod sursa (job #777626) | Cod sursa (job #2475090)
#include <cstdio>
#include <vector>
#include <set>
using namespace std;
typedef long long ll;
const int N = 1500 + 7;
const int M = 2500 + 7;
const int MOD = 104659;
int add(int a, int b)
{
a += b;
if (a >= MOD)
return a - MOD;
if (a < 0)
return a + MOD;
return a;
}
int mul(int a, int b)
{
return a * (ll) b % MOD;
}
int n, m, x[M], y[M], c[M];
vector <int> g[N];
int val[N];
bool u[N];
struct Edge
{
int from;
int to;
int cost;
};
bool operator < (Edge a, Edge b)
{
if (val[a.from] == val[b.from])
{
if (a.cost == b.cost)
return a.to < b.to;
else
return a.cost < b.cost;
}
else
return val[a.from] < val[b.from];
}
set <Edge> kek;
void ins(int a)
{
if (u[a])
return;
u[a] = 1;
for (auto &i : g[a])
{
int b = x[i] ^ y[i] ^ a;
kek.insert({a, b, c[i]});
}
}
Edge NO = {-1, -1, -1};
bool operator == (Edge a, Edge b)
{
return (a.from == b.from && a.to == b.to && a.cost == b.cost);
}
Edge get()
{
if (kek.empty())
return NO;
else
return *kek.begin();
}
pair <int, int> last = {0, 0};
int sol[N];
int cur = 1;
int main()
{
freopen ("dmin.in", "r", stdin);
freopen ("dmin.out", "w", stdout);
scanf("%d%d", &n, &m);
for (int i = 1; i <= m; i++)
{
scanf("%d%d%d", &x[i], &y[i], &c[i]);
g[x[i]].push_back(i);
g[y[i]].push_back(i);
}
sol[1] = 1;
ins(1);
while (1)
{
Edge it = get();
if (it == NO)
break;
kek.erase(it);
if (last != make_pair(val[it.from], it.cost))
{
if (u[it.to] == 0)
{
cur++;
last = {val[it.from], it.cost};
}
}
if (u[it.to] == 0)
val[it.to] = cur - 1;
if (cur - 1 == val[it.to])
{
sol[it.to] = add(sol[it.to], sol[it.from]);
}
ins(it.to);
}
for (int i = 2; i <= n; i++)
printf("%d ", sol[i]);
printf("\n");
return 0;
}