Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include <iostream>
- #include <cmath>
- #include <vector>
- #include <queue>
- #include <fstream>
- using namespace std;
- vector<pair<int, int> > graph[300];
- int n, m;
- struct node {
- int idx, shortest_path;
- node(int _idx, int _shortest_path) {
- idx = _idx;
- shortest_path = _shortest_path;
- }
- bool operator < (const node &tmp) const {
- return shortest_path > tmp.shortest_path;
- }
- };
- vector<int> dijkstra() {
- vector<bool> visited(n + 5, false);
- vector<int> dist(n + 5, 2e9);
- vector<int> path(n + 5, -1);
- priority_queue<node> pq;
- pq.push(node(1, 0));
- while(!pq.empty()) {
- node current = pq.top();
- pq.pop();
- visited[current.idx] = true;
- if(current.idx == n) {
- break;
- }
- for(int i = 0; i < graph[current.idx].size(); i++) {
- int sosed = graph[current.idx][i].first;
- int pat = graph[current.idx][i].second;
- if(!visited[sosed] and current.shortest_path + pat < dist[sosed]) {
- dist[sosed] = current.shortest_path + pat;
- pq.push(node(sosed, current.shortest_path + pat));
- path[sosed] = current.idx;
- }
- }
- }
- int A = 1, B = n;
- vector<int> result;
- while(B != A) {
- result.push_back(B);
- B = path[B];
- }
- result.push_back(A);
- return result;
- }
- int dijkstra_shortest_path() {
- vector<bool> visited(n + 5, false);
- vector<int> dist(n + 5, 2e9);
- priority_queue<node> pq;
- pq.push(node(1, 0));
- while(!pq.empty()) {
- node current = pq.top();
- pq.pop();
- visited[current.idx] = true;
- if(current.idx == n) {
- return current.shortest_path;
- }
- for(int i = 0; i < graph[current.idx].size(); i++) {
- int sosed = graph[current.idx][i].first;
- int pat = graph[current.idx][i].second;
- if(!visited[sosed] and current.shortest_path + pat < dist[sosed]) {
- dist[sosed] = current.shortest_path + pat;
- pq.push(node(sosed, current.shortest_path + pat));
- }
- }
- }
- return -2e9;
- }
- int main() {
- ios_base::sync_with_stdio(0);
- ifstream cin("rblock.in");
- ofstream cout("rblock.out");
- cin >> n >> m;
- for(int i = 0; i < m; i++) {
- int a, b, c;
- cin >> a >> b >> c;
- graph[a].push_back(make_pair(b, c));
- graph[b].push_back(make_pair(a, c));
- }
- vector<int> path = dijkstra();
- int initital_shortest = dijkstra_shortest_path();
- int maximum = 0;
- for(int i = 0; i + 1 < path.size(); i++) {
- int idx1 = -1;
- for(int j = 0; j < graph[path[i]].size(); j++) {
- if(graph[path[i]][j].first == path[i + 1]) {
- graph[path[i]][j].second *= 2;
- idx1 = j;
- break;
- }
- }
- int idx2 = -1;
- for(int j = 0; j < graph[path[i + 1]].size(); j++) {
- if(graph[path[i + 1]][j].first == path[i]) {
- graph[path[i + 1]][j].second *= 2;
- idx2 = j;
- break;
- }
- }
- maximum = max(maximum, dijkstra_shortest_path());
- graph[path[i]][idx1].second /= 2;
- graph[path[i + 1]][idx2].second /= 2;
- }
- cout << maximum - initital_shortest << endl;
- return 0;
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement