Pagini recente » Cod sursa (job #2959228) | Cod sursa (job #1676956) | Cod sursa (job #1731822) | Cod sursa (job #1806435) | Cod sursa (job #2230021)
#include<cstdio>
#include<vector>
#define MAX_N 100000
#define oo 0x3f3f3f3f
using namespace std;
vector<pair<int,int> >g[MAX_N+1];
int dist[MAX_N+1], h[MAX_N+1], pos[MAX_N+1], n, m, S, heapSize;
void readGraph() {
int i, x, y;
FILE* fin = fopen("bfs.in","r");
fscanf(fin,"%d%d%d",&n,&m,&S);
for(i = 0; i < m; i++) {
fscanf(fin,"%d%d",&x,&y);
g[x].push_back(make_pair(y,1));
}
fclose(fin);
}
inline void Swap(int i, int j) {
int aux = h[i];
h[i] = h[j];
h[j] = aux;
aux = pos[h[i]];
pos[h[i]] = pos[h[j]];
pos[h[j]] = aux;
}
void heapDown(int i) {
int l, r, p;
l = 2*i;
r = 2*i + 1;
if(l <= heapSize && dist[h[l]] < dist[h[i]])
p = l;
else p = i;
if(r <= heapSize && dist[h[r]] < dist[h[p]])
p = r;
if(p != i) {
Swap(i,p);
heapDown(p);
}
}
void heapUp(int i) {
while(dist[h[i]] < dist[h[i/2]]) {
Swap(i,i/2);
i >>= 1;
}
}
void Dijkstra(int s) {
vector<pair<int,int> >::iterator it;
int i, node;
heapSize = n;
for(i = 1; i <= n; i++) {
dist[i] = oo;
h[i] = pos[i] = i;
}
dist[s] = 0;
Swap(1,s);
for(i = 1; i <= n - 1; i++) {
node = h[1];
Swap(1,heapSize);
heapSize--;
heapDown(1);
for(it = g[node].begin(); it != g[node].end(); it++) {
if(dist[(*it).first] > dist[node] + (*it).second) {
dist[(*it).first] = dist[node] + (*it).second;
heapUp(pos[(*it).first]);
}
}
}
}
void printDistances() {
FILE* fout = fopen("bfs.out","w");
for(int i = 1; i <= n; i++)
if(dist[i] != oo)
fprintf(fout,"%d ",dist[i]);
else fprintf(fout,"-1 ");
fprintf(fout,"\n");
fclose(fout);
}
int main() {
readGraph();
Dijkstra(S);
printDistances();
return 0;
}