Cod sursa(job #1192417)

Utilizator Daniel30daniel Daniel30 Data 28 mai 2014 22:42:48
Problema Algoritmul lui Dijkstra Scor 10
Compilator cpp Status done
Runda Arhiva educationala Marime 0.93 kb
#include<cstdio>
#include<vector>
#include<queue>
using namespace std;

vector< vector< pair<int,int> > > vecini;
vector< pair<int,int> > t;
vector<int> dist;
queue<int> q;
 
int n,m,x,y,z,nod,cost,aux;
void dijkstra(){
	dist[1]=0;
	for(q.push(1);!q.empty(); q.pop()){
		aux=q.front();
		for(unsigned i=0; i<vecini[aux].size(); i++) {
			cost=vecini[aux][i].first; nod=vecini[aux][i].second;
			if(dist[nod]>dist[aux]+cost) {
				dist[nod]=dist[aux]+cost; q.push(nod);
			}
        }
    }
}
int main(){
	freopen("dijkstra.in","rt",stdin);
	freopen("dijkstra.out","wt",stdout);
	scanf("%d%d",&n,&m);
	vecini.assign(n+1,t);
	dist.assign(n+1,1<<30);
	pair<int,int> aux1;
	for(int i=0; i<m;i++) {
		scanf("%d%d%d",&x,&y,&z); 
		vecini[x].push_back(make_pair(z,y));
		vecini[y].push_back(make_pair(z,x));
	}
	dijkstra();
	for(int i=2; i<=n; i++) 
		printf("%d ",dist[i]!=1<<30 ? dist[i] : 0 );
	printf("\n");
	return 0;
}