Pagini recente » Rezultatele filtrării | Borderou de evaluare (job #2499065) | Monitorul de evaluare | Cod sursa (job #1575479) | Cod sursa (job #1767516)
#include <fstream>
#include <vector>
#include <climits>
#include <queue>
using namespace std;
ifstream fin("dijkstra.in");
ofstream fout("dijkstra.out");
queue <int> q;
struct vec
{
int cost;
int nr;
};
struct nod
{
bool viz=false;
int val=INT_MAX;
vector <vec> v;
};
nod g[50001];
int n, m;
void dij()
{
q.push(1);
while(!q.empty())
{
int t=q.front(); q.pop();
for(int i=0; i<g[t].v.size(); i++)
{
if(g[g[t].v[i].nr].val > g[t].val+g[t].v[i].cost)
{
g[g[t].v[i].nr].val = g[t].val+g[t].v[i].cost;
q.push(g[t].v[i].nr);
}
}
}
}
int main()
{
fin >> n >> m;
int x, y, k;
vec temp;
for(int i=1; i<=m; i++)
{
fin >> x >> y >> k;
temp.cost=k;
temp.nr=y;
g[x].v.push_back(temp);
}
g[1].viz=true;
g[1].val=0;
dij();
for(int i=2; i<=n; i++)
{
fout << g[i].val << " ";
}
return 0;
}