Advertisement
Josif_tepe

Untitled

Oct 4th, 2021
154
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 3.47 KB | None | 0 0
  1. #include <iostream>
  2. #include <cmath>
  3. #include <vector>
  4. #include <queue>
  5. #include <fstream>
  6. using namespace std;
  7. vector<pair<int, int> > graph[300];
  8. int n, m;
  9. struct node {
  10.     int idx, shortest_path;
  11.     node(int _idx, int _shortest_path) {
  12.         idx = _idx;
  13.         shortest_path = _shortest_path;
  14.     }
  15.     bool operator < (const node &tmp) const {
  16.         return shortest_path > tmp.shortest_path;
  17.     }
  18. };
  19. vector<int> dijkstra() {
  20.     vector<bool> visited(n + 5, false);
  21.     vector<int> dist(n + 5, 2e9);
  22.     vector<int> path(n + 5, -1);
  23.     priority_queue<node> pq;
  24.     pq.push(node(1, 0));
  25.     while(!pq.empty()) {
  26.         node current = pq.top();
  27.         pq.pop();
  28.         visited[current.idx] = true;
  29.        
  30.         if(current.idx == n) {
  31.             break;
  32.         }
  33.        
  34.         for(int i = 0; i < graph[current.idx].size(); i++) {
  35.             int sosed = graph[current.idx][i].first;
  36.             int pat = graph[current.idx][i].second;
  37.            
  38.             if(!visited[sosed] and current.shortest_path + pat < dist[sosed]) {
  39.                 dist[sosed] = current.shortest_path + pat;
  40.                 pq.push(node(sosed, current.shortest_path + pat));
  41.                 path[sosed] = current.idx;
  42.             }
  43.         }
  44.     }
  45.     int A = 1, B = n;
  46.     vector<int> result;
  47.     while(B != A) {
  48.         result.push_back(B);
  49.         B = path[B];
  50.     }
  51.     result.push_back(A);
  52.     return result;
  53. }
  54. int dijkstra_shortest_path() {
  55.     vector<bool> visited(n + 5, false);
  56.     vector<int> dist(n + 5, 2e9);
  57.     priority_queue<node> pq;
  58.     pq.push(node(1, 0));
  59.     while(!pq.empty()) {
  60.         node current = pq.top();
  61.         pq.pop();
  62.         visited[current.idx] = true;
  63.        
  64.         if(current.idx == n) {
  65.             return current.shortest_path;
  66.         }
  67.        
  68.         for(int i = 0; i < graph[current.idx].size(); i++) {
  69.             int sosed = graph[current.idx][i].first;
  70.             int pat = graph[current.idx][i].second;
  71.            
  72.             if(!visited[sosed] and current.shortest_path + pat < dist[sosed]) {
  73.                 dist[sosed] = current.shortest_path + pat;
  74.                 pq.push(node(sosed, current.shortest_path + pat));
  75.             }
  76.         }
  77.     }
  78.     return -2e9;
  79. }
  80. int main() {
  81.     ios_base::sync_with_stdio(0);
  82.     ifstream cin("rblock.in");
  83.     ofstream cout("rblock.out");
  84.     cin >> n >> m;
  85.     for(int i = 0; i < m; i++) {
  86.         int a, b, c;
  87.         cin >> a >> b >> c;
  88.         graph[a].push_back(make_pair(b, c));
  89.         graph[b].push_back(make_pair(a, c));
  90.     }
  91.    vector<int> path =  dijkstra();
  92.     int initital_shortest = dijkstra_shortest_path();
  93.     int maximum = 0;
  94.     for(int i = 0; i + 1 < path.size(); i++) {
  95.         int idx1 = -1;
  96.         for(int j = 0; j < graph[path[i]].size(); j++) {
  97.             if(graph[path[i]][j].first == path[i + 1]) {
  98.                 graph[path[i]][j].second *= 2;
  99.                 idx1 = j;
  100.                 break;
  101.             }
  102.         }
  103.         int idx2 = -1;
  104.         for(int j = 0; j < graph[path[i + 1]].size(); j++) {
  105.             if(graph[path[i + 1]][j].first == path[i]) {
  106.                 graph[path[i + 1]][j].second *= 2;
  107.                 idx2 = j;
  108.                 break;
  109.             }
  110.         }
  111.         maximum = max(maximum, dijkstra_shortest_path());
  112.         graph[path[i]][idx1].second /= 2;
  113.         graph[path[i + 1]][idx2].second /= 2;
  114.        
  115.     }
  116.     cout << maximum - initital_shortest << endl;
  117.     return 0;
  118. }
  119.  
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement