Pagini recente » Cod sursa (job #1846301) | Borderou de evaluare (job #2115201) | Cod sursa (job #2368090)
#include <iostream>
#include <set>
#include <vector>
#include <fstream>
#define MAX 250001
#define INF 99999999
using namespace std;
vector < pair<int,int> > graf[MAX];
int dist[MAX];
int main(){
ifstream be("dijkstra.in");
ofstream ki("dijkstra.out");
int n, m, to, from, weight;
be >> n >> m;
for (int i = 1; i<=m; i++){
be>>from>>to>>weight;
graf[from].push_back(make_pair(to, weight));
if(i>=2)
dist[i] = INF;
}
set < pair <int,int> > temp;
temp.insert(make_pair(0,1));
while(!temp.empty()){
int node = temp.begin() -> second;
temp.erase(temp.begin());
for( vector<pair <int, int> >::iterator it = graf[node].begin(); it != graf[node].end(); it++){
to = it->first;
weight = it->second;
if(dist[to]>dist[node]+weight){
if(dist[to]!=INF)
temp.erase(temp.find(make_pair(dist[to], to)));
dist[to]=dist[node]+weight;
temp.insert(make_pair(dist[to], to));
}
}
}
for(int i = 2; i <= n;i++){
if(dist[i] == INF){
dist[i] = 0;
}
ki << dist[i] << " ";
}
}