# Cod sursa(job #1981189)

Utilizator Data 15 mai 2017 05:26:50 Algoritmul lui Dijkstra 0 cpp done Arhiva educationala 1.29 kb
``````#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef vector<int> vi;
typedef pair<int,int> pii;
typedef pair<double, double> pdd;
#define pb push_back
#define mp make_pair
#define fs first
#define sc second
#define rep(i, from, to) for (int i = from; i < (to); ++i)
#define all(x) x.begin(), x.end()
#define sz(x) (int)(x).size()
#define FOR(i, to) for (int i = 0; i < (to); ++i)
typedef vector<vector<int> > vvi;
typedef vector<ll> vll;
typedef vector<vll> vvll;
typedef vector<pair<int, int> > vpi;
typedef pair<ll,ll> pll;
typedef vector<string> vs;
#define Nmax 2101010
int nx[Nmax];
int N, d[Nmax], viz[Nmax];
vector<pii> g[Nmax];
int M;
#define inf 101010000
priority_queue<pii, vector<pii>, greater<pii> > pq;
void dijkstra(int r) {
for(int i=1;i<=N;++i) d[i] = inf;
d[r] = 0; pq.push(mp(0,r));
while(!pq.empty()) {
int x = pq.top().sc; pq.pop(); viz[x] = 1;
for(auto a: g[x]) {
int y = a.fs, c = a.sc;
if(!viz[y]) {
if(d[y] > c + d[x]) {
d[y] = c + d[x]; pq.push(mp(d[y],y));
}
}
}
}
}

int main() {
freopen("dijkstra.in","r",stdin);
freopen("dijkstra.out","w",stdout);
cin >> N >> M;
FOR(i,M) {
int x,y,c;
cin >> x >> y >> c;
g[x].pb(mp(y,c));
}
dijkstra(1);
for(int i=2;i<=N;++i) cout << d[i] << " ";
}
``````