fork(1) download
copy 
  1. #include <cstdio>
  2. #include <iostream>
  3. #include <set>
  4. #include <map>
  5. #include <algorithm>
  6. #include <queue>
  7.  
  8. using namespace std;
  9.  
  10. typedef long long ll;
  11. typedef pair<int, int> pii;
  12.  
  13. struct DATA{
  14.     int u, last; 
  15. 	// u1 -> u -> u2
  16. 	// last > 0: tax[u] = cost[u1][u] = last
  17. 	// last < 0: tax[u] = cost[u][u2]
  18. 	ll cost;
  19. 	// last < 0: tax[u] haven't been added yet
  20. 	DATA(const int _u, const int _last, const ll _cost) {
  21. 		u = _u; last = _last; cost = _cost;
  22. 	}
  23. 	inline friend bool operator < (const DATA a, const DATA b) {
  24. 		return a.cost > b.cost;
  25. 	}
  26. };
  27.  
  28. int n, m;
  29. set<pii> a[100010], b[100010];
  30. priority_queue<DATA> f;
  31.  
  32. int main() {
  33. 	// freopen("TAX.inp", "r", stdin);
  34. 	// freopen("TAX.out", "w", stdout);
  35.  
  36. 	scanf("%d%d", &n, &m);
  37. 	for(int i = 1; i <= m; i++) {
  38. 		int u, v, c;
  39. 		scanf("%d%d%d", &u, &v, &c);
  40. 		a[u].insert(make_pair(c, v)); a[v].insert(make_pair(c, u));
  41. 		b[u].insert(make_pair(-c, v)); b[v].insert(make_pair(-c, u));
  42. 	}
  43. 	for(set<pii>::iterator it = a[1].begin(); it != a[1].end();) {
  44. 		pii V = *it; it++;
  45. 		f.push(DATA(V.second, V.first, 2*V.first));
  46. 		a[1].erase(V); a[V.second].erase(make_pair(V.first, 1));
  47. 	}
  48. 	for(set<pii>::iterator it = b[1].begin(); it != b[1].end();) {
  49. 		pii V = *it; it++;
  50. 		f.push(DATA(V.second, V.first, -V.first));
  51. 		b[1].erase(V); b[V.second].erase(make_pair(V.first, 1));	
  52. 	}
  53. 	while (!f.empty()) {
  54. 		DATA t = f.top(); f.pop();
  55. 		if (t.u == n) {
  56. 			if (t.last > 0) {
  57. 				printf("%lld\n", t.cost);
  58. 				return 0;
  59. 			}
  60. 			continue;
  61. 		}		
  62. 		if (t.last > 0) {
  63. 			for(set<pii>::iterator it = a[t.u].begin(); it != a[t.u].end();) {
  64. 				pii V = *it; it++;
  65. 				if (t.last < V.first) break;
  66. 				f.push(DATA(V.second, V.first, t.cost+V.first));
  67. 				f.push(DATA(V.second, -V.first, t.cost));
  68. 				a[t.u].erase(V); a[V.second].erase(make_pair(V.first, t.u));
  69. 			}
  70. 		}
  71. 		if (t.last < 0) {
  72. 			for(set<pii>::iterator it = b[t.u].begin(); it != b[t.u].end();) {
  73. 				pii V = *it; it++;
  74. 				if (t.last < V.first) break;
  75. 				f.push(DATA(V.second, -V.first, t.cost-2*V.first));
  76. 				f.push(DATA(V.second, V.first, t.cost-V.first));
  77. 				b[t.u].erase(V); b[V.second].erase(make_pair(V.first, t.u));	
  78. 			}
  79. 		}
  80. 	}
  81. 	return 0;		
  82. }
Success #stdin #stdout 0s 7548KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
https://ideone.com/eKdUIT
language:
C++ (gcc 8.3)
created:
11 years ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!