Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include <iostream>
- #include <vector>
- #include <set>
- #include <fstream>
- using namespace std;
- ifstream fin("dijkstra2.in");
- ofstream fout("dijkstra2.out");
- int drum[100005];
- vector<int> G[100005];
- vector<int> G_cost[100005];
- int n, m , start;
- long inf = -1;
- void citire()
- {
- fin >> n >> m >> start;
- int i;
- for(i = 1; i <= m; i++)
- {
- int x, y, c;
- fin >> x >> y >> c;
- G[x].push_back(y);
- G_cost[x].push_back(c);
- if(c > inf)
- inf = c;
- }
- inf = inf * (n - 1) + 1;
- }
- void dijsktra()
- {
- int i;
- for(i = 1; i <= n; i++)
- drum[i] = inf;
- drum[start] = 0;
- set<pair<int, int>> S;
- S.insert({drum[start], start});
- while(!S.empty())
- {
- int index = (*S.begin()).second;
- S.erase(S.begin());
- int lim = G[index].size();
- for(i = 0; i < lim; i++)
- {
- int vecin = G[index][i];
- if(drum[index] + G_cost[index][i] < drum[vecin])
- {
- S.erase({drum[vecin], vecin});
- drum[vecin] = drum[index] + G_cost[index][i];
- tata[vecin] = index;
- S.insert({drum[vecin], vecin});
- }
- }
- }
- for(i = 1; i <= n; i++)
- fout << drum[i] << " ";
- }
- int main()
- {
- citire();
- dijsktra();
- fin.close();
- fout.close();
- return 0;
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement