Pagini recente » Cod sursa (job #1708059) | Cod sursa (job #1702514) | Cod sursa (job #2422732)
//
// Created by Cristian Stern on 5/19/2019.
//
#include <iostream >
#include <fstream>
#include <vector>
#include <queue>
#define oo 0x3f3f3f3f
using namespace std;
int main(){
int n, m, x, y, cost;
//ifstream f("E:\\FMI\\AG\\lab3\\date.in");
ofstream g("dijkstra.out");
ifstream f("dijkstra.in");
f>>n>>m;
priority_queue <pair< int, int >> pq;
vector<vector<pair< int, int> > > G(n + 1);
vector < int > d(n + 1, oo);
vector < int > t(n + 1, 0);
for(int i = 0;i < m;i++){
f>>x>>y>>cost;
G[x].push_back(make_pair(cost, y));
}
int st = 1;
d[st] = 0;
pq.push(make_pair(0, st));
while(!pq.empty()){
pair < int, int> u = pq.top();
pq.pop();
for(auto v : G[u.second]){
if(d[v.second] > d[u.second] + v.first){
d[v.second] = d[u.second] + v.first;
t[v.second] = u.second;
pq.push(make_pair(d[v.second], v.second));
}
}
}
for(int i = 2;i <= n; i++)
if(d[i] == oo)
g<<0<<" ";
else g<<d[i]<<" ";
}