Cod sursa(job #2605846)

Utilizator dia.ionescuIonescu Diana dia.ionescu Data 25 aprilie 2020 22:45:13
Problema Algoritmul lui Dijkstra Scor 10
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.06 kb
#include<bits/stdc++.h>
using namespace std;
 
ifstream fin ("dijkstra.in");
ofstream fout ("dijkstra.out");
int n, m, x, y, w;
vector<vector<pair<int, int>>> graf;
vector<int> dist;
vector<int> tata;

int main()
{
    fin >> n >> m;

    for (int i=0; i<=n; ++i) {
        vector<pair<int, int> > aux;
        graf.push_back(aux);
        dist.push_back(20001);
        tata.push_back(0);
    }


    for (int i=1; i<=m; ++i) {
        fin >> x >> y >> w;
        pair <int, int> p;
        p.first=y;
        p.second=w;
        //sau p=make_pair(y, c);
        graf[x].push_back(p);
    }

  	priority_queue<pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>> > pq;
  	pq.push(make_pair(0, 1));
  	dist[1]=0;
		while(!pq.empty()) {
			int u = pq.top().second;
			pq.pop();
			for(int i = 0; i < graf[u].size(); i++) {
				int v = graf[u][i].first;
				w = graf[u][i].second;
				if  (dist[v] > dist[u] + w) {
					dist[v] = dist[u] + w;
					pq.push(make_pair(dist[v], v));
				}
			}
		}
    for (int i=2; i<=n; ++i) {
        fout << dist[i] << " ";
    }

    return 0;
}