Cod sursa(job #213345)

Utilizator za_wolfpalianos cristian za_wolf Data 9 octombrie 2008 15:52:35
Problema Algoritmul lui Dijkstra Scor 90
Compilator cpp Status done
Runda Arhiva educationala Marime 1.31 kb
#include<stdio.h>
#include<string.h>
#include<vector>
#include<queue>

using namespace std;

#define NMAX 50001
#define INF 50000100
int z[NMAX],d[NMAX],b,c,in,sf,i,j,n,m,k,l,a,s;
vector<int> x[NMAX], y[NMAX];
queue<int> q;
char ss[32],cc;
int main()
{
	freopen("dijkstra.in","r",stdin);
	freopen("dijkstra.out","w",stdout);
	scanf("%d%d%c",&n,&m,&cc);
	for (i=1;i<=m;i++)
	{
    	gets(ss);
        j=0;
        l=strlen(ss)-1;
        a=b=c=0;
        while (ss[j]!=' '&&j<=l)
        {
        	a=a*10+ss[j++]-48;
        }
        j++;
        while (ss[j]!=' '&&j<=l)
        {
        	b=b*10+ss[j++]-48;
        }
        j++;
        while (ss[j]!=' '&&j<=l)
        {
        	c=c*10+ss[j++]-48;
        }
        j++;
//		scanf("%d%d%d",&a,&b,&c);
        x[a].push_back(c);
		y[a].push_back(b);
	}
	q.push(1);
	for (i=2;i<=n;i++)
		d[i]=INF;
	z[1] = 1;
	while (!q.empty())
	{
		int nod = q.front(); q.pop();
		
		for (i=0;i<(int)y[nod].size();i++)
			if (d[nod]+x[nod][i]<d[y[nod][i]])
			{
				d[y[nod][i]]=d[nod]+x[nod][i];
				if (!z[y[nod][i]])
				{
					q.push(y[nod][i]);
					z[y[nod][i]]=1;
				}
			}
		z[nod]=0;
	}
	for (i=2;i<=n;i++)
		if (d[i]!=INF)
			printf("%d ",d[i]);
		else{
			printf("0 ");
			d[i] = 0;
		}
	printf("\n");


	return 0;
}