# Cod sursa(job #170300)

Utilizator Data 2 aprilie 2008 16:53:21 Drumuri minime 0 cpp done Arhiva de probleme 1.26 kb
``````#include <iostream>
#include <fstream>
#include <vector>

using namespace std;

typedef pair<int, int> pii;

#define MOD 104659

int N, M;
vector<pii> G[1501];

int dist[1501],
cnt[1501];

int q[1501];
bool inq[1501];
int begq, endq;

void dijkstra() {
for (int i(1); i <= N; ++i)
dist[i] = 1 << 30;

q[endq++] = 1;
inq[1] = true;
cnt[1] = 1;
dist[1] = 0;

while (begq != endq) {
int u = q[begq];

for (vector<pii>::iterator v = G[u].begin(); v != G[u].end(); ++v)
if (dist[u] + v->second < dist[v->first]) {
cnt[v->first] = cnt[u];
dist[v->first] = dist[u] + v->second;
if (!inq[v->first]) {
inq[v->first] = true;
q[endq] = v->first;
endq = (endq + 1) % N;
}
} else if (dist[u] + v->second == dist[v->first]) {
cnt[v->first] = (cnt[v->first] + cnt[u]) % MOD;
}

begq = (begq + 1) % N;
inq[u] = false;
}
}

int main(int argc, char *argv[]) {
FILE *fi = fopen("dmin.in", "r");
fscanf(fi, "%d %d", &N, &M);
int u, v, w;
for (int i(0); i < M; ++i) {
fscanf(fi, "%d %d %d", &u, &v, &w);
G[u].push_back(make_pair(v, w));
G[v].push_back(make_pair(u, w));
}
fclose(fi);

dijkstra();

FILE *fo = fopen("dmin.out", "w");
for (int i(2); i <= N; ++i)
fprintf(fo, "%d ", cnt[i]);
fprintf(fo, "\n");
fclose(fo);

return 0;
}

``````