Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include <iostream>
- #include<vector>
- #include<algorithm>
- #include <iomanip>
- using namespace std;
- vector<vector<pair<int, double>>> G;
- vector<int> used;
- vector<double> variability;
- int n;
- void dkstr(int v) {
- variability[v] = 1;
- for (int i = 0; i < n; i++) {
- //поиск минимума
- int max_v = -1;
- double max_ver = -1;
- for (int i = 0; i < n; i++) {
- if (used[i] == 0 && variability[i] > max_ver) {
- max_v = i;
- max_ver = variability[i];
- }
- }
- if (max_v == -1) {
- return;
- }
- //релаксация
- used[max_v] = 1;
- for (int i = 0; i < G[max_v].size(); i++) {
- int actual_v = G[max_v][i].first;
- double weight = G[max_v][i].second;
- if (used[actual_v] == 0 && variability[actual_v] < max_ver * weight) {
- variability[actual_v] = max_ver * weight;
- }
- }
- }
- }
- int main() {
- int m;
- cin >> n >> m;
- int s, f;
- cin >> s >> f;
- s -= 1;
- f -= 1;
- G = vector<vector<pair<int, double>>>(n);
- used = vector<int>(n);
- variability = vector<double>(n, -1);
- //ввод данных
- for (int i = 0; i < m; i++) {
- int fr, to, ver;
- cin >> fr >> to >> ver;
- fr--;
- to--;
- G[fr].push_back(make_pair(to, 1 - double(ver) / 100));
- G[to].push_back(make_pair(fr, 1 - double(ver) / 100));
- }
- dkstr(s);
- if (used[f] == 0) {
- cout << -1;
- } else {
- cout << fixed << 1 - variability[f] << '\n';
- }
- return 0;
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement